scientific article; zbMATH DE number 2038708

MaRDI QIDQ4449173zbMATH OpenFDO

Authors Rajiv Gandhi, Eran Halperin, Samir Khuller, Aravind Srinivasan, Guy Kortsarz

Publication date 8 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2719/27190164.htm

zbMATH Keywords

Approximation algorithmscapacitated coveringlinear programmingrandomized roundingset coververtex cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An improved approximation algorithm for vertex cover with hard capacities
• Capacitated vertex covering
• Covering Problems with Hard Capacities
• scientific article; zbMATH DE number 2119748
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs

Cited in

(14)

• Improved non-approximability results for minimum vertex cover with density constraints
• Algorithms and complexity results for the capacitated vertex cover problem
• Capacitated Arc Stabbing
• A PTAS for the cardinality constrained covering with unit balls
• An improved approximation algorithm for vertex cover with hard capacities
• Randomized rounding in the presence of a cardinality constraint
• Set cover revisited: hypergraph cover with hard capacities
• Covering Problems with Hard Capacities
• Linear time algorithms for approximating the facility terminal cover problem
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• Capacitated vertex covering
• scientific article; zbMATH DE number 2119748 (Why is no real title available?)
• On hard instances of approximate vertex cover
• The multi‐integer set cover and the facility terminal cover problem

This page was built for publication:

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