A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ/ log²logΔ) Rounds

2018/04/04 by Ben-Basat, Ran, Even, Guy, Kawarabayashi, Ken-ichi +1
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1804.01308

Abstract

We present a deterministic distributed 2-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is O(log n log Δ/ log² log Δ). This improves over the currently best known deterministic 2-approximation implied by [KVY94]. Our solution generalizes the (2+ε)-approximation algorithm of [BCS17], improving the dependency on ε^-1 from linear to logarithmic. In addition, for every ε=(log Δ)^-c, where c≥ 1 is a constant, our algorithm computes a (2+ε)-approximation in O(log Δ/ log log Δ)~rounds (which is asymptotically optimal).

Related

• A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ/εloglogΔ) Rounds
• Approximate Bipartite Vertex Cover in the CONGEST Model
• Optimal Distributed Covering Algorithms
• Optimal Distributed Weighted Set Cover Approximation
• Deterministic Distributed Dominating Set Approximation in the CONGEST\n Model