{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:06:25Z","timestamp":1768921585717,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T00:00:00Z","timestamp":1624924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1815901"],"award-info":[{"award-number":["CCF-1815901"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the <jats:italic>capacitated cycle covering problem<\/jats:italic>: given an undirected, complete graph <jats:italic>G<\/jats:italic> with metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(2 + \\frac{2}{7})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mn>7<\/mml:mn>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a <jats:inline-formula><jats:alternatives><jats:tex-math>$$2 + \\epsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03f5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> lower bound for the relaxation.<\/jats:p>","DOI":"10.1007\/s10107-021-01678-3","type":"journal-article","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T14:27:09Z","timestamp":1624976829000},"page":"497-518","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A fast $$(2 + \\frac{2}{7})$$-approximation algorithm for capacitated cycle covering"],"prefix":"10.1007","volume":"192","author":[{"given":"Vera","family":"Traub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3350-7337","authenticated-orcid":false,"given":"Thorben","family":"Tr\u00f6bst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,29]]},"reference":[{"issue":"4","key":"1678_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"K Altinkemer","year":"1987","unstructured":"Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"key":"1678_CR2","unstructured":"Becker, A.: A tight 4\/3 approximation for capacitated vehicle routing in trees. In: Blais, E., Jansen, K., Rolim, J.D.P., Steurer, D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0116, pp. 3:1\u20133:15. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"1678_CR3","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0112, pp. 8:1\u20138:15. Schloss Dagstuhl\u2013Leibniz\u2013Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"1678_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-030-24766-9_8","volume-title":"Algorithms and Data Structures","author":"A Becker","year":"2019","unstructured":"Becker, A., Klein, P.N., Schild, A.: A PTAS for bounded-capacity vehicle routing in planar graphs. In: Friggstad, Z., Sack, J.R., Salavatipour, M.R. (eds.) Algorithms and Data Structures, pp. 99\u2013111. Springer International Publishing, Cham (2019)"},{"key":"1678_CR5","doi-asserted-by":"crossref","unstructured":"Blauth, J., Traub, V., Vygen, J.: Improving the approximation ratio for capacitated vehicle routing. arXiv:1907.08304 (2020)","DOI":"10.1007\/978-3-030-73879-2_1"},{"issue":"4","key":"1678_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.disopt.2006.04.002","volume":"3","author":"A Bompadre","year":"2006","unstructured":"Bompadre, A., Dror, M., Orlin, J.B.: Improved bounds for vehicle routing solutions. Discrete Optim. 3(4), 299\u2013316 (2006)","journal-title":"Discrete Optim."},{"issue":"3","key":"1678_CR7","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10107-004-0506-y","volume":"100","author":"R Carr","year":"2004","unstructured":"Carr, R., Vempala, S.: On the Held\u2013Karp relaxation for the asymmetric and symmetric traveling salesman problems. Math. Program. 100(3), 569\u2013587 (2004)","journal-title":"Math. Program."},{"issue":"1","key":"1678_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manag. Sci."},{"issue":"1","key":"1678_CR9","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00453-014-9906-4","volume":"73","author":"A Das","year":"2015","unstructured":"Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73(1), 115\u2013142 (2015)","journal-title":"Algorithmica"},{"key":"1678_CR10","unstructured":"Das, S., Jain, L., Kumar, N.: A constant factor approximation for capacitated min-max tree cover. arXiv:1907.08304 (2019), to appear in APPROX\/RANDOM 2020"},{"key":"1678_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.disopt.2017.02.003","volume":"25","author":"I Diarrassouba","year":"2017","unstructured":"Diarrassouba, I.: On the complexity of the separation problem for rounded capacity inequalities. Discrete Optim. 25, 86\u2013104 (2017)","journal-title":"Discrete Optim."},{"issue":"4","key":"1678_CR12","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.orl.2003.11.010","volume":"32","author":"G Even","year":"2004","unstructured":"Even, G., Garg, N., Koenemann, J., Ravi, R., Sinha, A.: Min-max tree covers of graphs. Oper. Res. Lett. 32(4), 309\u2013315 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1678_CR13","first-page":"335","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69(1), 335\u2013349 (1995)","journal-title":"Math. Program."},{"issue":"4","key":"1678_CR14","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Kan, A.H.G.R.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"1678_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-319-44914-2_16","volume-title":"Discrete Optimization and Operations Research","author":"M Khachay","year":"2016","unstructured":"Khachay, M., Dubinin, R.: PTAS for the Euclidean capacitated vehicle routing problem in $${\\mathbb{R}}^d$$. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) Discrete Optimization and Operations Research, pp. 193\u2013205. Springer International Publishing, Cham (2016)"},{"issue":"4","key":"1678_CR16","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1287\/opre.39.4.616","volume":"39","author":"M Labb\u00e9","year":"1991","unstructured":"Labb\u00e9, M., Laporte, G., Mercure, H.: Capacitated vehicle routing on trees. Oper. Res. 39(4), 616\u2013622 (1991)","journal-title":"Oper. Res."},{"key":"1678_CR17","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/11538462_14","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"J Ma\u00dfberg","year":"2005","unstructured":"Ma\u00dfberg, J., Vygen, J.: Approximation algorithms for network design and facility location with service capacities. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 158\u2013169. Springer, Berlin, Heidelberg (2005)"},{"issue":"1","key":"1678_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s12532-016-0108-8","volume":"9","author":"D Pecin","year":"2017","unstructured":"Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.: Improved branch-cut-and-price for capacitated vehicle routing. Math. Program. Comput. 9(1), 61\u2013100 (2017)","journal-title":"Math. Program. Comput."},{"key":"1678_CR19","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-030-17953-3_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Pessoa","year":"2019","unstructured":"Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: A generic exact solver for vehicle routing and related problems. In: Lodi, A., Nagarajan, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 354\u2013369. Springer International Publishing, Cham (2019)."},{"key":"1678_CR20","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Cham (2003)"},{"key":"1678_CR21","unstructured":"Tr\u00f6bst, T.: Capacitated vehicle routing and cycle covering problems. Master\u2019s Thesis, Research Institute for Discrete Mathematics, University of Bonn (2019)"},{"issue":"3","key":"1678_CR22","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1016\/j.ejor.2013.09.045","volume":"234","author":"T Vidal","year":"2014","unstructured":"Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234(3), 658\u2013673 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"1678_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.tcs.2016.01.041","volume":"654","author":"W Yu","year":"2016","unstructured":"Yu, W., Liu, Z.: Improved approximation algorithms for some min\u2013max and minimum cycle cover problems. Theor. Comput. Sci. 654, 45\u201358 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1678_CR24","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10878-018-0268-8","volume":"37","author":"W Yu","year":"2019","unstructured":"Yu, W., Liu, Z.: Better approximability results for min\u2013max tree\/cycle\/path cover problems. J. Comb. Optim. 37(2), 563\u2013578 (2019)","journal-title":"J. Comb. Optim."},{"key":"1678_CR25","doi-asserted-by":"crossref","unstructured":"Yu, W., Liu, Z., Bao, X.: New approximation algorithms for the minimum cycle cover problem. Theor. Comput. Sci. (2019)","DOI":"10.1016\/j.tcs.2019.04.009"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01678-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01678-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01678-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:19:18Z","timestamp":1646846358000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01678-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,29]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1678"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01678-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,29]]},"assertion":[{"value":"29 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}