Iterative partial rounding for vertex cover with hard capacities

DOI10.1137/1.9781611974782.174MaRDI QIDQ4575923zbMATH OpenOpenAlexFDO

Authors Mong-Jen Kao

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Iterative partial rounding for vertex cover with hard capacities
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Tight approximation for partial vertex cover with hard capacities
• Tight approximation for partial vertex cover with hard capacities
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs

Cited in

(12)

• O(f) bi-criteria approximation for capacitated covering with hard capacities
• Capacitated covering problems in geometric spaces
• Iterative partial rounding for vertex cover with hard capacities
• Tight approximation for partial vertex cover with hard capacities
• New developments in iterated rounding (invited talk)
• Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• Capacitated covering problems in geometric spaces
• Tight approximation for partial vertex cover with hard capacities
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• scientific article; zbMATH DE number 7758357 (Why is no real title available?)
• Improved bounds for metric capacitated covering problems
• Improved approximation algorithm for capacitated facility location with uniform facility cost

This page was built for publication: Iterative partial rounding for vertex cover with hard capacities

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