{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T03:11:46Z","timestamp":1775272306062,"version":"3.50.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030046507","type":"print"},{"value":"9783030046514","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_35","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T14:56:50Z","timestamp":1542293810000},"page":"522-536","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Star Routing: Between Vehicle Routing and Vertex Cover"],"prefix":"10.1007","author":[{"given":"Diego","family":"Delle Donne","sequence":"first","affiliation":[]},{"given":"Guido","family":"Tagliavini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"EM Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, H.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197\u2013218 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90008-6. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0166218X94900086","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"35_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.jalgor.2005.01.010","volume":"57","author":"M de Berg","year":"2005","unstructured":"de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22\u201336 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2005.01.010. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677405000246","journal-title":"J. Algorithms"},{"key":"35_CR3","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"issue":"4","key":"35_CR4","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1287\/opre.12.4.568","volume":"12","author":"G Clarke","year":"1964","unstructured":"Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568\u2013581 (1964)","journal-title":"Oper. Res."},{"issue":"3","key":"35_CR5","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1287\/trsc.23.3.208","volume":"23","author":"JR Current","year":"1989","unstructured":"Current, J.R., Schilling, D.A.: The covering salesman problem. Transp. Sci. 23(3), 208\u2013213 (1989). http:\/\/www.jstor.org\/stable\/25768381","journal-title":"Transp. Sci."},{"issue":"4","key":"35_CR6","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. America 2(4), 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. America"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Rudoy, M.: A simple proof that the $$(n^2-1)$$-puzzle is hard. Computing Research Repository abs\/1707.03146 (2017)","DOI":"10.1016\/j.tcs.2018.04.031"},{"key":"35_CR8","first-page":"2005","volume":"162","author":"I Dinur","year":"2004","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 2005 (2004)","journal-title":"Ann. Math."},{"issue":"1","key":"35_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0196-6774(03)00047-6","volume":"48","author":"A Dumitrescu","year":"2003","unstructured":"Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for tsp with neighborhoods in the plane. J. Algorithms 48(1), 135\u2013159 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(03)00047-6. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677403000476. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms","journal-title":"J. Algorithms"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, pp. 10\u201322. STOC 1976. ACM, New York, NY, USA (1976)","DOI":"10.1145\/800113.803626"},{"issue":"2","key":"35_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/net.3230070203","volume":"7","author":"BL Golden","year":"1977","unstructured":"Golden, B.L., Magnanti, T.L., Nguyen, H.Q.: Implementing vehicle routing algorithms. Networks 7(2), 113\u2013148 (1977)","journal-title":"Networks"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph TSP. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science. p. 640. FOCS 1995. IEEE Computer Society, Washington, DC, USA (1995)","DOI":"10.1109\/SFCS.1995.492665"},{"issue":"3","key":"35_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1002\/net.3230060305","volume":"6","author":"JK Lenstra","year":"1976","unstructured":"Lenstra, J.K., Kan, A.H.G.R.: On general routing problems. Networks 6(3), 273\u2013280 (1976)","journal-title":"Networks"},{"issue":"1","key":"35_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/net.3230040105","volume":"4","author":"CS Orloff","year":"1974","unstructured":"Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4(1), 35\u201364 (1974)","journal-title":"Networks"},{"issue":"4","key":"35_CR15","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1145\/76359.76361","volume":"36","author":"LK Platzman","year":"1989","unstructured":"Platzman, L.K., Bartholdi III, J.J.: Spacefilling curves and the planar travelling salesman problem. J. ACM 36(4), 719\u2013737 (1989)","journal-title":"J. ACM"},{"issue":"c","key":"35_CR16","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/j.asoc.2014.08.057","volume":"24","author":"MH Shaelaie","year":"2014","unstructured":"Shaelaie, M.H., Salari, M., Naji-Azimi, Z.: The generalized covering traveling salesman problem. Appl. Soft Comput. 24(c), 867\u2013878 (2014). https:\/\/doi.org\/10.1016\/j.asoc.2014.08.057","journal-title":"Appl. Soft Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T02:32:04Z","timestamp":1775269924000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}