A Distributed (2+epsilon)-Approximation for Vertex Cover in O(log Delta/epsilon log log Delta) Rounds

作者：Bar Yehuda Reuven^*; Censor Hillel Keren; Schwartzman Gregory

来源：Journal of the ACM, 2017, 64(3): 23.

DOI：10.1145/3060294

• Distributed computing
• approximation algorithms
• vertex cover
• local-ratio
• graph algorithms

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 maximum degree in the graph, for any epsilon > 0 that is at most O(1). For a constant epsilon, this implies a constant approximation in O(log Delta / log log Delta) rounds, which contradicts the lower bound of [KMW10].

• 出版日期2017-6