A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover

Abstract

The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).

conference version appeared in IPCO'93

Cited by in corpus (5)

• Distributed algorithms for covering, packing and maximum weighted matching
• Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time
• Parallel Approximation Algorithms for Facility-Location Problems
• LP-based Covering Games with Low Price of Anarchy
• Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings