Set cover revisited: hypergraph cover with hard capacities

DOI10.1007/978-3-642-31594-7_64MaRDI QIDQ2843299zbMATH OpenOpenAlexFDO

Authors Barna Saha, Samir Khuller

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31594-7_64

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(11)

• FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
• Tight approximation for partial vertex cover with hard capacities
• Iterative partial rounding for vertex cover with hard capacities
• O(f) bi-criteria approximation for capacitated covering with hard capacities
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Online flexible busy time scheduling on heterogeneous machines
• On capacitated set cover problems
• Covering Problems with Hard Capacities
• O(f) bi-approximation for capacitated covering with hard capacities
• The multi‐integer set cover and the facility terminal cover problem
• Tight approximation for partial vertex cover with hard capacities

This page was built for publication: Set cover revisited: hypergraph cover with hard capacities

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