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

We present a simple deterministic distributed $(2+ε)$-approximation algorithm for minimum weight vertex cover, which completes in $O(\logΔ/ε\log\logΔ)$ rounds, where $Δ$ 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Δ/\log\logΔ)$ rounds, which contradicts the lower bound of [KMW10].

No reviews yet.

No comments yet.