A Distributed $(2+\epsilon)$-Approximation for Vertex Cover in $O(\log{\Delta}/\epsilon\log\log{\Delta})$ Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman · arXiv (Cornell University) · 2016
We present a simple deterministic distributed $(2+\epsilon)$-approximation algorithm for minimum weight vertex cover, which completes in $O(\log{\Delta}/\epsilon\log\log{\Delta})$ rounds, where $\Delta$ is the maximum degree in the graph, for any $\epsilon>0$ which is at most $O(1)$. For a constant $\epsilon$, this implies a constant approximation in $O(\log{\Delta}/\log\log{\Delta})$ rounds, which contradicts the lower bound of [KMW10].