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

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 max…