{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:10Z","timestamp":1759638730825},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p> In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length L. <\/jats:p>","DOI":"10.1142\/s1793830912500449","type":"journal-article","created":{"date-parts":[[2012,9,25]],"date-time":"2012-09-25T15:17:45Z","timestamp":1348586265000},"page":"1250044","source":"Crossref","is-referenced-by-count":5,"title":["THE TRAVELING SALESMAN PROBLEM FOR LINES AND RAYS IN THE PLANE"],"prefix":"10.1142","volume":"04","author":[{"given":"ADRIAN","family":"DUMITRESCU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin\u2013Milwaukee, WI 53201-0784, USA"}]}],"member":"219","published-online":{"date-parts":[[2013,1,4]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009467"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9516-3"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00259-9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000143"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000212"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00146-0"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830912500449","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:14:14Z","timestamp":1565111654000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830912500449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2013,1,4]]},"published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1142\/S1793830912500449"],"URL":"https:\/\/doi.org\/10.1142\/s1793830912500449","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]}}}