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

DOI10.1006/JAGM.1994.1036MaRDI QIDQ4312226zbMATH OpenOpenAlexFDO

Authors Samir Khuller, Uzi Vishkin, Neal E. Young

Publication date 30 November 1994

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0205037

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

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).

Cited in

(9)

• Parallel algorithm for minimum partial dominating set in unit disk graph
• Parallel approximation for partial set cover
• Set cover problems with small neighborhood covers
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Optimal distributed covering algorithms
• Approximation algorithms in combinatorial scientific computing
• Parallel approximation of optimization problems
• Distributed algorithms for covering, packing and maximum weighted matching
• Towards distributed two-stage stochastic optimization

This page was built for publication: A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4312226)