{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T13:55:33Z","timestamp":1768398933955,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T00:00:00Z","timestamp":1402531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00453-014-9906-4","type":"journal-article","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T13:41:50Z","timestamp":1402494110000},"page":"115-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":40,"title":["A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing"],"prefix":"10.1007","volume":"73","author":[{"given":"Aparna","family":"Das","sequence":"first","affiliation":[]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,12]]},"reference":[{"key":"9906_CR1","volume-title":"Algorithms and Computation","author":"A Adamaszek","year":"2009","unstructured":"Adamaszek, A., Czumaj, A., Lingas, A.: PTAS for k-tour cover problem on the plane for moderately large values of k. Algorithms and Computation. Springer-Verlag, Berlin (2009)"},{"issue":"5","key":"9906_CR2","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(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"9906_CR3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: A survey. Math. Program. 97(1\u20132), 43\u201369 (2003)","journal-title":"Math. Program."},{"issue":"5","key":"9906_CR4","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.1137\/S0097539701399654","volume":"32","author":"S Arora","year":"2003","unstructured":"Arora, S., Karakostas, G.: Approximation schemes for minimum latency problems. SIAM J. Comput. 32(5), 1317\u20131337 (2003)","journal-title":"SIAM J. Comput."},{"key":"9906_CR5","doi-asserted-by":"crossref","unstructured":"Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k. Research Report RT0162, IBM Tokyo Research Laboratory (1996)","DOI":"10.1145\/258533.258602"},{"key":"9906_CR6","doi-asserted-by":"crossref","unstructured":"Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k. In: STOC \u201997: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 275\u2013283, ACM, New York (1997)","DOI":"10.1145\/258533.258602"},{"key":"9906_CR7","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Euclidean steiner forest. In: FOCS \u201908: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 115\u2013124, IEEE Computer Society, Washington DC (2008)","DOI":"10.1109\/FOCS.2008.59"},{"key":"9906_CR8","unstructured":"Cardon, S., Dommers, S., Eksin, C., Sitters, R., Stougie, A., Stougie. L.: A PTAS for the multiple depot vehicle routing problem. SPOR Reports, January 2008. www.win.tue.nl\/bs\/spor\/ . Accessed 9 June 2014"},{"key":"9906_CR9","doi-asserted-by":"crossref","unstructured":"Czumaj A., Lingas, A.: A polynomial time approximation scheme for Euclidean minimum cost k-connectivity. In ICALP \u201998: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pp. 682\u2013694, Springer-Verlag, London (1998)","DOI":"10.1007\/BFb0055093"},{"issue":"1","key":"9906_CR10","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. Manag. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manag. Sci."},{"key":"9906_CR11","doi-asserted-by":"crossref","unstructured":"Das A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: SODA \u201910: Proceedings of the Twenty First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia (2009)","DOI":"10.1137\/1.9781611973075.33"},{"key":"9906_CR12","series-title":"Network routing","first-page":"1","volume-title":"Handbooks in Operations Research and Management Science","author":"M Fisher","year":"1995","unstructured":"Fisher, M., Fisher, M.: Chapter 1 vehicle routing. In: Monma, C.L., Ball, M.O., Magnanti, T.L., Nemhauser, G.L. (eds.) Handbooks in Operations Research and Management Science. Network routing, vol. 8, pp. 1\u201333. Elsevier, Oxford (1995)"},{"key":"9906_CR13","volume-title":"Operations Research\/Computer Science Interfaces Series","author":"B Golden","year":"2008","unstructured":"Golden, B., Raghavan, S., Wasil, E.: The vehicle routing problem: latest advances and new challenges. Operations Research\/Computer Science Interfaces Series, vol. 43. Springer, New York (2008)"},{"issue":"4","key":"9906_CR14","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":"9906_CR15","unstructured":"Haimovich, M., Rinnooy Kan, A.H.G., Stougie, L.: Analysis of heuristics for vehicle routing problems. In: Vehicle Routing: Methods and Studies. Management Science Systems, vol. 16, pp. 47\u201361, Elsevier Science B.V., Amsterdam (1988)"},{"issue":"1","key":"9906_CR16","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0402010","volume":"2","author":"H Karloff","year":"1989","unstructured":"Karloff, H.: How long can a Euclidean traveling salesman tour be? SIAM J. Discr. Math. 2(1), 91\u201399 (1989)","journal-title":"SIAM J. Discr. Math."},{"issue":"3","key":"9906_CR17","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean k-median problem. SIAM J. Comput. 37(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9906_CR18","first-page":"64","volume":"2","author":"CL Li","year":"1990","unstructured":"Li, C.L., Simchi-Levi, D.: Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. INFORMS 2(1), 64\u201373 (1990)","journal-title":"INFORMS"},{"issue":"4","key":"9906_CR19","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JSB Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9906_CR20","doi-asserted-by":"crossref","unstructured":"Rao, S.B., Smith, W.D.: Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d. In: STOC \u201998: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 540\u2013550, ACM, New York (1998)","DOI":"10.1145\/276698.276868"},{"key":"9906_CR21","doi-asserted-by":"crossref","unstructured":"Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: STOC \u201906: Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, pp. 316\u2013325, ACM, New York (2006)","DOI":"10.1145\/1132516.1132563"},{"key":"9906_CR22","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 (2001)"},{"key":"9906_CR23","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer-Verlag, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9906-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9906-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9906-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T08:48:06Z","timestamp":1565513286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9906-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,12]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9906"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9906-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,12]]}}}