{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T03:33:00Z","timestamp":1791171180505,"version":"4.1.0"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We consider the classical vertex cover and set cover problems with hard capacity constraints. This means that a set (vertex) can cover only a limited number of its elements (adjacent edges), and the number of available copies of each set (vertex) is bounded. This is a natural generalization of the classical problems which also captures resource limitations in practical scenarios. We obtain the following results. For the unweighted vertex cover problem with hard capacities we give a 3\u2010approximation algorithm that is based on randomized rounding with alterations. We prove that the weighted version is at least as hard as the set cover problem, yielding an interesting separation between the approximability of weighted and unweighted versions of a \u201cnatural\u201d graph problem. A logarithmic approximation factor for both the set cover and the weighted vertex cover problem with hard capacities follows from the work of Wolsey [Combinatorica, 2 (1982), pp. 385\u2013393] on submodular set cover. We provide here a simple and intuitive proof for this bound.<\/jats:p>","DOI":"10.1137\/s0097539703422479","type":"journal-article","created":{"date-parts":[[2006,8,24]],"date-time":"2006-08-24T15:30:58Z","timestamp":1156433458000},"page":"498-515","source":"Crossref","is-referenced-by-count":62,"title":["Covering Problems with Hard Capacities"],"prefix":"10.1137","volume":"36","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"(Seffi) Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/1018115"},{"key":"R2","unstructured":"J. Bar\u2010ilan, G. Kortsarz, and D. Peleg,\n                      Generalized submodular cover problems and applications\n                      , in Proceedings of the 4th Israel Symposium on Theory of Computing and Systems, Jerusalem, Israel, 1996, IEEE Computer Society Press, Piscataway, NJ, 1996, pp. 110\u2013118."},{"key":"R3","first-page":"27","volume":"25","author":"Bar\u2010Yehuda R.","year":"1985","journal-title":"Ann. Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-5060","issn-type":"print"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Y. Bartal, M. Charikar, and D. Raz,\n                      \n                        Approximating min\u2010sum\n                        k\n                        \u2010clustering in metric spaces\n                      \n                      , in Proceedings of 33rd ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, 2001, ACM, New York, 2001, pp. 11\u201320.","DOI":"10.1145\/380752.380754"},{"key":"R5","unstructured":"R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips,\n                      Strengthening integrality gaps for capacitated network design and covering problems\n                      , in Proceedings of the 11th ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2000, SIAM, Philadelphia, 2000, pp. 106\u2013115."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Charikar, S. Guha, E. Tardos, and D. Shmoys,\n                      \n                        A constant\u2010factor approximation algorithm for the\n                        k\n                        \u2010median problem\n                      \n                      , in Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1999, ACM, New York, 1999, pp. 1\u201310.","DOI":"10.1145\/301250.301257"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.21.5.591"},{"key":"R8","unstructured":"J. Chuzhoy and Y. Rabani,\n                      \n                        Approximating\n                        k\n                        \u2010median with non\u2010uniform capacities\n                      \n                      , in Proceedings of the 16th ACM\u2010SIAM Symposium on Discrete Algorithms, Vancouver, BC, Canada, 2005, SIAM, Philadelphia, 2005, pp. 952\u2013958."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.4.515"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan,\n                      An improved approximation algorithm for vertex cover with hard capacities\n                      , in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Eindhoven, The Netherlands, 2003, Lecture Notes in Comput. Sci. 2719, Springer, New York, 2003, pp. 164\u2013175.","DOI":"10.1007\/3-540-45061-0_15"},{"key":"R13","unstructured":"R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan,\n                      Dependent rounding in bipartite graphs\n                      , in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada, 2002, IEEE Press, Piscataway, NJ, pp. 323\u2013332."},{"key":"R14","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R15","unstructured":"R. S. Garfinkel and G. L. Nemhauser,\n                      Optimal set covering: A survey\n                      , in Perspectives on Optimization: A Collection of Expository Articles, A. M. Geofrion, ed., Addison\u2010Wesley, Reading, MA, 1972, pp. 164\u2013193."},{"key":"R16","unstructured":"N. Garg, R. Khandekar, and V. Pandit,\n                      Improved approximation for universal facility location\n                      , in Proceedings of the 16th ACM\u2010SIAM Symposium on Discrete Algorithms, Vancouver, BC, Canada, 2005, SIAM, Philadelphia, 2005, pp. 959\u2013960."},{"key":"R17","unstructured":"S. Guha, R. Hassin, S. Khuller, and E. Or,\n                      Capacitated vertex covering with applications\n                      , in Proceedings of the 13th ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, CA, 2002, SIAM, Philadelphia, 2002, pp. 858\u2013865."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"R19","unstructured":"D. S. Hochbaum, ED.\n                      Approximation Algorithms for NP\u2010Hard Problems\n                      , PWS Publishing, Toronto, 1996."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos and N. E. Young,\n                      Tight approximation results for general covering integer programs\n                      , in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, 2001, IEEE Press, Piscataway, NJ, pp. 522\u2013528.","DOI":"10.1109\/SFCS.2001.959928"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M. Mahdian and M. P\u00e1l,\n                      Universal facility location\n                      , in Proceedings of the 11th Annual European Symposium on Algorithms, Budapest, Hungary, 2003, Lecture Notes in Comput. Sci. 2832, Springer, New York, 2003, pp. 409\u2013422.","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"R25","unstructured":"P. B. Mirchandani and R. L. Francis, eds.\n                      Discrete Location Theory\n                      , Wiley\u2010Interscience, New York, 1990."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70831-8"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. Aardal,\n                      Approximation algorithms for the facility location problem\n                      , in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, El Paso, TX, 1997, ACM, New York, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"M. P\u00e1l, \u00c9. Tardos, and T. Wexler,\n                      Facility location with nonuniform hard capacities\n                      , in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, 2001, IEEE Press, Piscataway, NJ, pp. 329\u2013338.","DOI":"10.1109\/SFCS.2001.959907"},{"key":"R29","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer\u2010Verlag, New York, 2001."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0125"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703422479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:27:42Z","timestamp":1787336862000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703422479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539703422479"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703422479","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}