{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T11:17:19Z","timestamp":1742642239697,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST107-2218-E-194-015-MY3","MOST108-2221-E-194-026-MY3"],"award-info":[{"award-number":["MOST107-2218-E-194-015-MY3","MOST108-2221-E-194-026-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00453-020-00749-9","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T07:05:38Z","timestamp":1596438338000},"page":"45-71","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Iterative Partial Rounding for Vertex Cover with Hard Capacities"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7238-3093","authenticated-orcid":false,"given":"Mong-Jen","family":"Kao","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"issue":"1\u20132","key":"749_CR1","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10107-014-0857-y","volume":"154","author":"H-C An","year":"2015","unstructured":"An, H.-C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated $$k$$-center. Math. Program. 154(1\u20132), 29\u201353 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"749_CR2","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"H-C An","year":"2017","unstructured":"An, H.-C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. SIAM J. Comput. 46(1), 272\u2013306 (2017)","journal-title":"SIAM J. Comput."},{"key":"749_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: ESA\u201912, pp. 133\u2013144 (2012)","DOI":"10.1007\/978-3-642-33090-2_13"},{"issue":"2","key":"749_CR4","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"2","key":"749_CR5","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. ACM Trans. Algorithms 13(2), 23:1\u201323:31 (2017)","journal-title":"ACM Trans. Algorithms"},{"key":"749_CR6","doi-asserted-by":"crossref","unstructured":"Cheung, W.-C., Goemans, M., Wong, S.: Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: SODA\u201914 (2014)","DOI":"10.1137\/1.9781611973402.124"},{"key":"749_CR7","doi-asserted-by":"publisher","unstructured":"Chuzhoy, J., Naor, J.: Covering problems with hard capacities. In: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS) 2002, 16\u201319 November 2002, Vancouver, BC, Canada, pp. 481\u2013489. IEEE Computer Society (2002). https:\/\/doi.org\/10.1109\/SFCS.2002.1181972","DOI":"10.1109\/SFCS.2002.1181972"},{"issue":"2","key":"749_CR8","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1137\/S0097539703422479","volume":"36","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Naor, J.: Covering problems with hard capacities. SIAM J. Comput. 36(2), 498\u2013515 (2006)","journal-title":"SIAM J. Comput."},{"issue":"(23\u201324)","key":"749_CR9","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1016\/j.ipl.2011.09.004","volume":"111","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than O($$2^n$$). Inf. Process. Lett 111((23\u201324)), 1099\u20131103 (2011)","journal-title":"Inf. Process. Lett"},{"key":"749_CR10","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: IWPEC\u201908, pp. 78\u201390 (2008)","DOI":"10.1007\/978-3-540-79723-4_9"},{"key":"749_CR11","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jcss.2005.06.004","volume":"72","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72, 16\u201333 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"749_CR12","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324\u2013360 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"749_CR13","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"749_CR14","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/06065310X","volume":"38","author":"F Grandoni","year":"2008","unstructured":"Grandoni, F., K\u00f6nemann, J., Panconesi, A., Sozio, M.: A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput. 38(3), 825\u2013840 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"749_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S Guha","year":"2003","unstructured":"Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering. J. Algorithms 48(1), 257\u2013270 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"749_CR16","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"749_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"749_CR18","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the $$k$$-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"749_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-013-9844-6","volume":"72","author":"M-J Kao","year":"2015","unstructured":"Kao, M.-J., Chen, H.-L., Lee, D.T.: Capacitated domination: problem complexity and approximation algorithms. Algorithmica 72, 1\u201343 (2015)","journal-title":"Algorithmica"},{"issue":"2","key":"749_CR20","first-page":"274","volume":"60","author":"M-J Kao","year":"2011","unstructured":"Kao, M.-J., Liao, C.-S., Lee, D.T.: Algorithmica. Capacitated domination problem 60(2), 274\u2013300 (2011)","journal-title":"Capacitated domination problem"},{"issue":"5","key":"749_CR21","doi-asserted-by":"publisher","first-page":"1800","DOI":"10.1007\/s00453-018-0506-6","volume":"81","author":"M-J Kao","year":"2019","unstructured":"Kao, M.-J., Tu, H.-L., Lee, D.T.: An O($$f$$) bi-approximation for weighted capacitated covering with hard capacities. Algorithmica 81(5), 1800\u20131817 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"749_CR22","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon$$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"749_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45\u201358 (2013)","journal-title":"Inf. Comput."},{"issue":"2","key":"749_CR24","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/2983633","volume":"13","author":"S Li","year":"2017","unstructured":"Li, S.: On uniform capacitated $$k$$-median beyond the natural lp relaxation. ACM Trans. Algorithms 13(2), 22:1\u201322:18 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"749_CR25","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. SIAM J. Comput. 45(2), 530\u2013547 (2016)","journal-title":"SIAM J. Comput."},{"key":"749_CR26","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.dam.2012.10.021","volume":"168","author":"M Liedloff","year":"2014","unstructured":"Liedloff, M., Todinca, I., Villanger, Y.: Solving capacitated dominating set by using covering by subsets and maximum matching. Discret. Appl. Math. 168, 60\u201368 (2014)","journal-title":"Discret. Appl. Math."},{"key":"749_CR27","doi-asserted-by":"crossref","unstructured":"Saha, B., Khuller, S.: Set cover revisited: hypergraph cover with hard capacities. In: ICALP\u201912, pp. 762\u2013773 (2012)","DOI":"10.1007\/978-3-642-31594-7_64"},{"key":"749_CR28","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"issue":"4","key":"749_CR29","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00749-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00749-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00749-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T23:14:57Z","timestamp":1627946097000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00749-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["749"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00749-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"7 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}