A Distributed $(2+\epsilon )$-Approximation for Vertex Cover in $O(\log \Delta /\epsilon \log \log \Delta )$ Rounds

Abstract

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].