Loading...
Please wait, while we are loading the content...
Similar Documents
A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O ( log n log ∆ / log 2 log ∆ ) Rounds
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ben-Basat, Ran Even, Guy Kawarabayashi, Ken-Ichi Schwartzman, Gregory |
| Copyright Year | 2018 |
| Abstract | We present a deterministic distributed 2-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is O(log n log ∆/ log log ∆). This improves over the currently best known deterministic 2-approximation implied by [KVY94]. Our solution generalizes the (2 + ǫ)-approximation algorithm of [BCS17], improving the dependency on ǫ from linear to logarithmic. In addition, for every ǫ = (log ∆), where c ≥ 1 is a constant, our algorithm computes a (2 + ǫ)-approximation in O(log ∆/ log log ∆) rounds (which is asymptotically optimal). Technion, Department of Computer Science, sran@cs.technion.ac.il. This work was partially sponsored by the Technion-HPI reseach school. Tel Aviv University, guy@eng.tau.ac.il. NII, Japan, k_keniti@nii.ac.jp, greg@nii.ac.jp . This work was supported by JST ERATO Grant Number JPMJER1201, Japan. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://export.arxiv.org/pdf/1804.01308 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
