{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T02:25:43Z","timestamp":1768616743342,"version":"3.49.0"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030247652","type":"print"},{"value":"9783030247669","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_8","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"99-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Amariah","family":"Becker","sequence":"first","affiliation":[]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[]},{"given":"Aaron","family":"Schild","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"8_CR1","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: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 275\u2013283. ACM (1997)","DOI":"10.1145\/258533.258602"},{"key":"8_CR2","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14\u201316 October 1996, pp. 184\u2013193 (1996)"},{"key":"8_CR3","unstructured":"Becker, A.: A tight 4\/3 approximation for capacitated vehicle routing in trees. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"8_CR4","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for k-center and bounded-capacity vehicle routing in metrics with bounded highway dimension. CoRR abs\/1707.08270 (2017). http:\/\/arxiv.org\/abs\/1707.08270"},{"key":"8_CR5","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"8_CR6","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: 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"8_CR7","unstructured":"Becker, A., Paul, A.: A PTAS for minimum makespan vehicle routing in trees. arXiv preprint arXiv:1807.04308 (2018)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. In: 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 761\u2013770 (2008)","DOI":"10.1109\/FOCS.2008.79"},{"key":"8_CR9","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report , Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976)"},{"key":"8_CR10","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. SIAM (2010)","DOI":"10.1137\/1.9781611973075.33"},{"issue":"3","key":"8_CR11","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-662-47672-7_38","volume-title":"Automata, Languages, and Programming","author":"Andreas Emil Feldmann","year":"2015","unstructured":"Feldmann, A.E., Fung, W.S., K\u00f6nemann, J., Post, I.: A (1+$$\\varepsilon $$)-embedding of low highway dimension graphs into bounded treewidth graphs. In: 42nd International Colloquium on Automata, Languages, and Programming, pp. 469\u2013480 (2015)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1137\/1.9781611975482.66","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Eli Fox-Epstein","year":"2019","unstructured":"Fox-Epstein, E., Klein, P.N., Schild, A.: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1069\u20131088. SIAM (2019)"},{"issue":"4","key":"8_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., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","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 $$R^d$$. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 193\u2013205. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-44914-2_16"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: 36th Annual ACM Symposium on Theory of Computing, pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24766-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:52:55Z","timestamp":1710265975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}