{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T03:06:21Z","timestamp":1782183981503,"version":"3.54.5"},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p> In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek to find a tour of minimum length which visits at least one point in each region. We give (i) an O(\u03b1)-approximation algorithm for the case when the regions are disjoint and \u03b1-fat, with possibly varying size; (ii) an O(\u03b1<jats:sup>3<\/jats:sup>)-approximation algorithm for intersecting \u03b1-fat regions with comparable diameters. These results also apply to the case with continuous neighborhoods, where the sought TSP tour can hit each region at any point. We also give (iii) a simple O( log n)-approximation algorithm for continuous non-fat neighborhoods. The most distinguishing features of these algorithms are their simplicity and low running-time complexities. <\/jats:p>","DOI":"10.1142\/s0218195909002897","type":"journal-article","created":{"date-parts":[[2009,5,5]],"date-time":"2009-05-05T07:30:21Z","timestamp":1241508621000},"page":"173-193","source":"Crossref","is-referenced-by-count":42,"title":["APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS"],"prefix":"10.1142","volume":"19","author":[{"given":"KHALED","family":"ELBASSIONI","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123 Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ALEKSEI V.","family":"FISHKIN","sequence":"additional","affiliation":[{"name":"Siemens AG, Corporate Technology, Discrete Optimization, Otto-Hahn-Ring 6, 81739 M\u00fcnchen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"REN\u00c9","family":"SITTERS","sequence":"additional","affiliation":[{"name":"Econometrics and Operations Research, the VU University, Amsterdam, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"rf2","first-page":"1","volume":"45","author":"Arora S.","journal-title":"J. ACM"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.01.010"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"rf10","first-page":"469","volume":"6","author":"Gudmundsson J.","journal-title":"Nordic J. Comput."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"rf14","doi-asserted-by":"crossref","unstructured":"J. S. B.\u00a0Mitchell, ch. Geometric Shortest Paths and Network Optimization (Elsevier, North-Holland, Amsterdam, 2000)\u00a0pp. 633\u2013701.","DOI":"10.1016\/B978-044482537-7\/50016-4"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909002897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:22:41Z","timestamp":1565122961000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909002897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":8,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1142\/S0218195909002897"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909002897","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]}}}