{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T10:47:43Z","timestamp":1769251663612,"version":"3.49.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319449135","type":"print"},{"value":"9783319449142","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-44914-2_16","type":"book-chapter","created":{"date-parts":[[2016,11,29]],"date-time":"2016-11-29T21:56:02Z","timestamp":1480456562000},"page":"193-205","source":"Crossref","is-referenced-by-count":25,"title":["PTAS for the Euclidean Capacitated Vehicle Routing Problem in $$R^d$$"],"prefix":"10.1007","author":[{"given":"Michael","family":"Khachay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Dubinin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,10]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","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, 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"16_CR2","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":"16_CR3","unstructured":"Cardon, S., Dommers, S., Eksin, C., Sitters, R., Stougie, A., Stougie, L.: A PTAS for the multiple depot vehicle routing problem. Technical Report 2008.03, Eindhoven Univ. of Technology, March 2008. http:\/\/www.win.tue.nl\/bs\/spor\/2008-03.pdf"},{"key":"16_CR4","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)"},{"issue":"1","key":"16_CR5","doi-asserted-by":"crossref","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. Manage. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manage. Sci."},{"key":"16_CR6","doi-asserted-by":"crossref","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. pp. 390\u2013403. SODA 2010, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2010)","DOI":"10.1137\/1.9781611973075.33"},{"key":"16_CR7","doi-asserted-by":"crossref","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, 115\u2013142 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"16_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1134\/S1064562416010233","volume":"93","author":"EK Gimadi","year":"2016","unstructured":"Gimadi, E.K., Rykov, I.A.: On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math. 93(1), 117\u2013120 (2016)","journal-title":"Dokl. Math."},{"key":"16_CR9","series-title":"Operations Research\/Computer Science Interfaces Series","volume-title":"The Vehicle Routing Problem: Latest Advances and New Challenges","year":"2008","unstructured":"Golden, B.L., Raghavan, S., Wasil, E.A. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research\/Computer Science Interfaces Series, vol. 43. Springer, Heidelberg (2008)"},{"issue":"4","key":"16_CR10","doi-asserted-by":"crossref","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."},{"key":"16_CR11","series-title":"SpringerBriefs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-17939-1","volume-title":"Spherical Radial Basis Functions, Theory and Applications","author":"S Hubbert","year":"2015","unstructured":"Hubbert, S., Gia, Q.T.L., Morton, T.M.: Spherical Radial Basis Functions, Theory and Applications. SpringerBriefs in Mathematics, 1st edn. Springer International Publishing, Heidelberg (2015)","edition":"1"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Khachay, M., Neznakhina, K.: Approximability of the minimum-weight k-size cycle cover problem. J. Global Optim. (2015). http:\/\/dx.doi.org\/10.1007\/s10898-015-0391-3","DOI":"10.1007\/s10898-015-0391-3"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/978-3-319-26626-8_14","volume-title":"9th International Conference on Combinatorial Optimization and Applications, COCOA 2015","author":"M Khachay","year":"2015","unstructured":"Khachay, M., Zaytseva, H.: Polynomial time approximation scheme for single-depot euclidean capacitated vehicle routing problem. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 178\u2013190. Springer, Cham (2015). http:\/\/dx.doi.org\/10.1007\/978-3-319-26626-8_14"},{"key":"16_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":"16_CR15","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 4, 237\u2013244 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR16","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780199563074.001.0001","volume-title":"Introduction to Metric and Topological Spaces","author":"WA Sutherland","year":"2009","unstructured":"Sutherland, W.A.: Introduction to Metric and Topological Spaces, 2nd edn. Oxford University Press, Oxford (2009). [Oxford Mathematics]","edition":"2"},{"key":"16_CR17","volume-title":"The Vehicle Routing Problem","year":"2001","unstructured":"Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001)"}],"container-title":["Lecture Notes in Computer Science","Discrete Optimization and Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44914-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:43:53Z","timestamp":1718919833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44914-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449135","9783319449142"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44914-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}