A Distributed $(2+ϵ)$-Approximation for Vertex Cover in $O(\log \mathrm{\Delta }\mathrm{/}ϵ\log \log \mathrm{\Delta })$ Rounds

We present a simple deterministic distributed $(2+ϵ)$-approximation algorithm for minimum weight vertex cover, which completes in $O(\log \mathrm{\Delta }\mathrm{/}ϵ\log \log \mathrm{\Delta })$ rounds, where $\mathrm{\Delta }$ is the maximum degree in the graph, for any $ϵ>0$ which is at most $O(1)$. For a constant $ϵ$, this implies a constant approximation in $O(\log \mathrm{\Delta }\mathrm{/}\log \log \mathrm{\Delta })$ rounds, which contradicts the lower bound of [KMW10].