A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

DOI10.1137/06065310XMaRDI QIDQ3631893zbMATH OpenOpenAlexFDO

Authors Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio

Publication date 22 June 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/06065310x

zbMATH Keywords

approximation algorithmsdistributed algorithmsprimal-dual algorithmsvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• Distributed set cover approximation: primal-dual with optimal locality
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• Capacitated vertex covering

Cited in

(11)

• O(f) bi-criteria approximation for capacitated covering with hard capacities
• Iterative partial rounding for vertex cover with hard capacities
• Capacitated Arc Stabbing
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Tight approximation for partial vertex cover with hard capacities
• On the weighted \(k\)-path vertex cover problem
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Tight approximation for partial vertex cover with hard capacities
• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• Distributed algorithms for covering, packing and maximum weighted matching
• Approximating bipartite minimum vertex cover in the Congest model

This page was built for publication: A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

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