A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman · Journal of the ACM · 2017
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 that 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].