Approximation of Partial Capacitated Vertex Cover

DOI10.1137/080728044MaRDI QIDQ5892615zbMATH OpenOpenAlexFDO

Authors Guy Flysher, Julián Mestre, Reuven Bar-Yehuda, Dror Rawitz

Publication date 18 July 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmspartial coveringcapacitated coveringlocal ratio techniqueprize collecting covering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• Approximation of Partial Capacitated Vertex Cover
• Tight approximation for partial vertex cover with hard capacities
• Tight approximation for partial vertex cover with hard capacities
• scientific article; zbMATH DE number 2119748
• An approximation algorithm for the partial vertex cover problem in hypergraphs
• On approximation of max-vertex-cover
• Approximation algorithms for the partition vertex cover problem
• Approximation algorithms for the partition vertex cover problem
• scientific article; zbMATH DE number 1947055
• An improved approximation algorithm for vertex cover with hard capacities

Cited in

(9)

• Approximation algorithms for partial vertex covers in trees
• Capacitated vertex covering
• scientific article; zbMATH DE number 7561427 (Why is no real title available?)
• Tight approximation for partial vertex cover with hard capacities
• The approximability of partial vertex covers in trees
• O(f) bi-criteria approximation for capacitated covering with hard capacities
• Approximation of Partial Capacitated Vertex Cover
• Replica Placement via Capacitated Vertex Cover
• Tight approximation for partial vertex cover with hard capacities

This page was built for publication: Approximation of Partial Capacitated Vertex Cover

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