{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:47:58Z","timestamp":1768924078180,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319266251","type":"print"},{"value":"9783319266268","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26626-8_14","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T04:08:43Z","timestamp":1449634123000},"page":"178-190","source":"Crossref","is-referenced-by-count":15,"title":["Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem"],"prefix":"10.1007","author":[{"given":"Michael","family":"Khachay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helen","family":"Zaytseva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,9]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, C., Czumaj, A., Lingas, A.: PTAS for k-tour cover problem on the plane for moderately large values of k. Manuscript 1 (2009)","DOI":"10.1007\/978-3-642-10631-6_100"},{"issue":"5","key":"14_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: a polynomial time approximation scheme for fixed k. IBM Tokyo Research (1996)","DOI":"10.1145\/258533.258602"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Caric, T., Gold, H.: Vehicle Routing Problem. InTech (2008)","DOI":"10.5772\/64"},{"key":"14_CR5","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"G Dantzig","year":"1959","unstructured":"Dantzig, G., Ramser, J.: The truck dispatching problem. Manage. Sci. 6, 80\u201391 (1959)","journal-title":"Manage. Sci."},{"key":"14_CR7","unstructured":"Das, A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 390\u2013403. Society for Industrial and Applied Mathematics, Philadelphia (2010). \n                      http:\/\/dl.acm.org\/citation.cfm?id=1873601.1873634"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00453-014-9906-4","volume":"73","author":"A Das","year":"2014","unstructured":"Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73, 115\u2013142 (2014)","journal-title":"Algorithmica"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.disopt.2014.09.003","volume":"14","author":"VG Deineko","year":"2014","unstructured":"Deineko, V.G., Klinz, B., Tiskin, A., Woeginger, G.J.: Four-point conditions for the TSP: the complete complexity classification. Discrete Optim. 14, 147\u2013159 (2014)","journal-title":"Discrete Optim."},{"key":"14_CR10","series-title":"perations Research\/Computer Science Interfaces","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","year":"2008","unstructured":"Golden, B., Raghavan, S., Wasil, E. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. perations Research\/Computer Science Interfaces, 1st edn. Springer, US (2008)","edition":"1"},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1134\/S1064562415020313","volume":"91","author":"M Khachai","year":"2015","unstructured":"Khachai, M., Neznakhina, E.: Approximability of the problem about a minimum-weight cycle cover of a graph. Doklady Math. 91(2), 240\u2013245 (2015). \n                      http:\/\/dx.doi.org\/10.1134\/S1064562415020313","journal-title":"Doklady Math."},{"issue":"1","key":"14_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1134\/S0081543815050107","volume":"289","author":"M Khachai","year":"2015","unstructured":"Khachai, M., Neznakhina, E.: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proc. Steklov Inst. Math. 289(1), 111\u2013125 (2015). \n                      http:\/\/dx.doi.org\/10.1134\/S0081543815050107","journal-title":"Proc. Steklov Inst. Math."},{"key":"14_CR14","first-page":"66","volume":"4","author":"S Kumar","year":"2012","unstructured":"Kumar, S., Panneerselvam, R.: A survey on the vehicle routing problem and its variants. Intell. Inf. Manage. 4, 66\u201374 (2012)","journal-title":"Intell. Inf. Manage."},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"J Lenstra","year":"1981","unstructured":"Lenstra, J., Rinnooy Kan, A.: Complexity of vehicle routing and scheduling problems. Networks 11, 221\u2013227 (1981)","journal-title":"Networks"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/060676003","volume":"38","author":"B Manthey","year":"2008","unstructured":"Manthey, B.: On approximating restricted cycle covers. SIAM J. Comput. 38, 181\u2013206 (2008)","journal-title":"SIAM J. Comput."},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"1470","DOI":"10.1016\/j.dam.2008.10.005","volume":"157","author":"B Manthey","year":"2009","unstructured":"Manthey, B.: Minimum-weight cycle covers and their approximability. Discrete Appl. Math. 157, 1470\u20131480 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C Papadimitriou","year":"1997","unstructured":"Papadimitriou, C.: Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4(3), 237\u2013244 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzales, T.: P-complete approximation problems. J. ACM 23, 555\u2013565 (1976)","journal-title":"J. ACM"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications, SIAM (2001)","DOI":"10.1137\/1.9780898718515"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26626-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T17:05:35Z","timestamp":1559322335000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26626-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319266251","9783319266268"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26626-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}