LIPIcs.ISAAC.2016.40.pdf
- Filesize: 0.91 MB
- 12 pages
Document
O(f) Bi-Approximation for Capacitated Covering with Hard Capacities
Authors
-
Part of:
Volume:
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-12-07
Cite AsGet BibTex
Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee. O(f) Bi-Approximation for Capacitated Covering with Hard Capacities. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 40:1-40:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.40
https://doi.org/10.4230/LIPIcs.ISAAC.2016.40
Abstract
We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity.
In this paper we present an O(f) bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k geq 2, a cover with a cost ratio of (1+ frac{1}{k - 1})(f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f^2 via augmenting the available multiplicity by a factor of f.
Keywords
- Capacitated Covering
- Hard Capacities
- Bi-criteria Approximation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Reuven Bar-Yehuda and Shimon Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198-203, 1981. URL: http://dx.doi.org/10.1016/0196-6774(81)90020-1.
- Reuven Bar-Yehuda, Guy Flysher, Julián Mestre, and Dror Rawitz. Approximation of partial capacitated vertex cover. SIAM Journal on Discrete Mathematics, 24(4):1441-1469, 2010. URL: http://dx.doi.org/10.1137/080728044.
- W.-C. Cheung, M. Goemans, and S. Wong. Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In SODA'14, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.124.
- Julia Chuzhoy and Joseph Naor. Covering problems with hard capacities. SIAM Journal on Computing, 36(2):498-515, August 2006. URL: http://dx.doi.org/10.1137/S0097539703422479.
- Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, and Aravind Srinivasan. An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci., 72:16-33, February 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.06.004.
- F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio. A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput., 38(3), 2008. URL: http://dx.doi.org/10.1137/06065310X.
- Sudipto Guha, Refael Hassin, Samir Khuller, and Einat Or. Capacitated vertex covering. Journal of Algorithms, 48(1):257-270, August 2003. URL: http://dx.doi.org/10.1016/S0196-6774(03)00053-1.
- Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555-556, 1982. URL: http://dx.doi.org/10.1137/0211045.
-
Mong-Jen Kao. An Algorithmic Approach to Local and Global Resource Allocations. PhD thesis, National Taiwan University, 2012.
-
Mong-Jen Kao. Iterative partial rounding for vertex cover with hard capacities. manuscript, 2016.
- Mong-Jen Kao, Han-Lin Chen, and D.T. Lee. Capacitated domination: Problem complexity and approximation algorithms. Algorithmica, November 2013. URL: http://dx.doi.org/10.1007/s00453-013-9844-6.
- Mong-Jen Kao, Chung-Shou Liao, and D. T. Lee. Capacitated domination problem. Algorithmica, 60(2):274-300, June 2011. URL: http://dx.doi.org/10.1007/s00453-009-9336-x.
- Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335-349, May 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.019.
- Barna Saha and Samir Khuller. Set cover revisited: Hypergraph cover with hard capacities. In ICALP'12, pages 762-773, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_64.
- L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982. URL: http://dx.doi.org/10.1007/BF02579435.