A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

DOI10.1137/06065310XzbMath1187.68707OpenAlexW2056399203MaRDI QIDQ3631893

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

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 algorithmsvertex coverprimal-dual algorithms

Mathematics Subject Classification ID

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

Related Items (9)

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

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