{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T09:09:11Z","timestamp":1769850551371,"version":"3.49.0"},"reference-count":26,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,8,1]],"date-time":"2003-08-01T00:00:00Z","timestamp":1059696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[2003,8]]},"DOI":"10.1016\/s0196-6774(03)00047-6","type":"journal-article","created":{"date-parts":[[2003,5,27]],"date-time":"2003-05-27T23:51:31Z","timestamp":1054079491000},"page":"135-159","source":"Crossref","is-referenced-by-count":165,"title":["Approximation algorithms for TSP with neighborhoods in the plane"],"prefix":"10.1016","volume":"48","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"Joseph S.B.","family":"Mitchell","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(03)00047-6_BIB001","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0166-218X(94)90008-6","article-title":"Approximation algorithms for the geometric covering salesman problem","volume":"55","author":"Arkin","year":"1994","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"10.1016\/S0196-6774(03)00047-6_BIB002","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/290179.290180","article-title":"Nearly linear time approximation schemes for Euclidean TSP and other geometric problems","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB003","first-page":"829","article-title":"Visibility in the plane","author":"Asano","year":"2000"},{"issue":"4","key":"10.1016\/S0196-6774(03)00047-6_BIB004","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","article-title":"Fast algorithms for geometric traveling salesman problems","volume":"4","author":"Bentley","year":"1992","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB005","first-page":"187","article-title":"TSP with neighborhoods of varying size","author":"de Berg","year":"2002"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB006","series-title":"Geometric Inequalities","author":"Bottema","year":"1969"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB007","unstructured":"P. Berman, M. Karpinski, On some tighter inapproximability results, Technical Report TR98-065, ECCC, 1998"},{"issue":"3","key":"10.1016\/S0196-6774(03)00047-6_BIB008","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/PL00009467","article-title":"Finding the shortest watchman route in a simple polygon","volume":"22","author":"Carlsson","year":"1999","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB009","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB010","first-page":"469","article-title":"A fast approximation algorithm for TSP with neighborhoods","volume":"6","author":"Gudmundsson","year":"1999","journal-title":"Nordic J. Comput."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB011","unstructured":"J. Gudmundsson, C. Levcopoulos, Hardness result for TSP with neighborhoods, Technical Report LU-CS-TR:2000-216, Department of Computer Science, Lund University, Sweden, 2000"},{"issue":"3","key":"10.1016\/S0196-6774(03)00047-6_BIB012","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0020-0190(01)00259-9","article-title":"The traveling salesman problem for lines in the plane","volume":"82","author":"Jonsson","year":"2002","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB013","first-page":"225","article-title":"The traveling salesman problem","author":"J\u00fcnger","year":"1995"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB014","year":"1985"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB015","first-page":"360","article-title":"Approximation algorithms for geometric tour and network design problems","author":"Mata","year":"1995"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB016","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","article-title":"Linear programming in linear time when the dimension is fixed","volume":"31","author":"Megiddo","year":"1984","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/S0196-6774(03)00047-6_BIB017","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","article-title":"Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems","volume":"28","author":"Mitchell","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB018","unstructured":"J.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: Part III. Faster polynomial-time approximation schemes for geometric network optimization, Manuscript, University at Stony Brook, 1997"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB019","first-page":"229","article-title":"Approximation algorithms for geometric optimization problems","author":"Mitchell","year":"1997"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB020","first-page":"633","article-title":"Geometric shortest paths and network optimization","author":"Mitchell","year":"2000"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB021","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"The Euclidean traveling salesman problem is NP-complete","volume":"4","author":"Papadimitriou","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB022","series-title":"The Enjoyment of Mathematics","author":"Rademacher","year":"1957"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB023","first-page":"540","article-title":"Approximating geometrical graphs via \u201cspanners\u201d and \u201cbanyans\u201d","author":"Rao","year":"1998"},{"key":"10.1016\/S0196-6774(03)00047-6_BIB024","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1287\/ijoc.4.2.206","article-title":"Fast heuristics for large geometric traveling salesman problems","volume":"4","author":"Reinelt","year":"1992","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0196-6774(03)00047-6_BIB025","unstructured":"O. Schwartz, S. Safra, On the complexity of approximating TSP with neighborhoods and related problems, Manuscript, July 2002, submitted"},{"issue":"1","key":"10.1016\/S0196-6774(03)00047-6_BIB026","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0020-0190(00)00146-0","article-title":"Fast computation of shortest watchman routes in simple polygons","volume":"77","author":"Tan","year":"2001","journal-title":"Inform. Process. Lett."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000476?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000476?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T07:21:27Z","timestamp":1553152887000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677403000476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0196677403000476"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(03)00047-6","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}