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

2016/02/11 by Bar-Yehuda, Reuven, Censor-Hillel, Keren, Schwartzman, Gregory
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1602.03713

Abstract

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

Related

• A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log nlogΔ/ log²logΔ) Rounds
• Optimal Distributed Covering Algorithms
• Optimal Distributed Weighted Set Cover Approximation
• Approximate Bipartite Vertex Cover in the CONGEST Model
• Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs