{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T21:17:10Z","timestamp":1783113430948,"version":"3.54.6"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540275800","type":"print"},{"value":"9783540316916","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_90","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"1115-1126","source":"Crossref","is-referenced-by-count":39,"title":["Approximation Algorithms for Euclidean Group TSP"],"prefix":"10.1007","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksei V.","family":"Fishkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nabil H.","family":"Mustafa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"90_CR1","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","volume":"55","author":"E.M. Arkin","year":"1994","unstructured":"Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics\u00a055(3), 197\u2013218 (1994)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"90_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Nearly linear time approximation schemes for euclidean TSP and other geometric problems. J. ACM\u00a045(5), 1\u201330 (1998)","journal-title":"J. ACM"},{"key":"90_CR3","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, GSIA, Carnegie-Mellon University (1976)"},{"key":"90_CR4","doi-asserted-by":"crossref","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. In: Proceedings 10th Annual European Symposium on algorithms (ESA), pp. 187\u2013199 (2002)","DOI":"10.1007\/3-540-45749-6_20"},{"issue":"1","key":"90_CR5","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\u00a048(1), 135\u2013159 (2003)","journal-title":"J. Algorithms"},{"key":"90_CR6","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proceedings 8th Annual ACM Symposium on the Theory of Computing, STOC (1976)","DOI":"10.1145\/800113.803626"},{"issue":"1","key":"90_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the Group Steiner Tree Problem. J. Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"90_CR8","unstructured":"Gudmundsson, J., Levcopoulos, C.: Hardness result for TSP with neighborhoods, Technical Report LU-CS-TR:2000-216, Department of Computer Science, Lund University, Sweden (2000)"},{"issue":"4","key":"90_CR9","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivions approximate polygonal subdivisons: A simple polynomial-time approximation scheme for geometric TSP, k-MST and related problems. SICOMP\u00a028(4), 1298\u20131309 (1999)","journal-title":"SICOMP"},{"key":"90_CR10","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"J.S.B. Mitchel","year":"2000","unstructured":"Mitchel, J.S.B.: Geometric shortest paths and network optimization. In: Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, North-Holland, Amsterdam (2000)"},{"key":"90_CR11","doi-asserted-by":"crossref","unstructured":"Mata, C.S., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems (extended abstract). In: Proceedings 11th Ann. ACM Symposium on Computational Geometry, pp. 360\u2013369 (1995)","DOI":"10.1145\/220279.220318"},{"issue":"3","key":"90_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science\u00a04(3), 237\u2013244 (1977)","journal-title":"Theoretical Computer Science"},{"key":"90_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-52292-1_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G. Reich","year":"1990","unstructured":"Reich, G., Widmayer, P.: Beyond steiner\u2019s problem: a VLSI oriented generalization. In: Nagl, M. (ed.) WG 1989. LNCS, vol.\u00a0411, pp. 196\u2013210. Springer, Heidelberg (1990)"},{"key":"90_CR14","doi-asserted-by":"crossref","unstructured":"Slavik, P.: A tight analysis of the greedy algorithm for set cover. In: STOC 1996: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 435\u2013441 (1996)","DOI":"10.1145\/237814.237991"},{"key":"90_CR15","unstructured":"Slavik, P.: The errand scheduling problem. Technical report, March 14, Technical Report, SUNY, Buffalo, USA (1997)"},{"key":"90_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-540-39658-1_41","volume-title":"Algorithms - ESA 2003","author":"S. Safra","year":"2003","unstructured":"Safra, S., Schwartz, O.: On the complexity of approximating TSP with Neighborhoods and related problems. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 446\u2013458. Springer, Heidelberg (2003)"},{"key":"90_CR17","doi-asserted-by":"crossref","unstructured":"van der Stappen, A.F.: Motion Planning amidst Fat Obstacles. Ph.d. dissertation, Utrecht University, Utrecht, Netherlands (1994)","DOI":"10.1145\/177424.177453"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_90.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:19Z","timestamp":1605643579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11523468_90","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}