{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T15:26:49Z","timestamp":1648740409208},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2004,4]]},"abstract":"<jats:p> In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n \u220a-separated segments in two dimensional space. Our results are based on an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique<jats:sup>5<\/jats:sup> for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n<jats:sup>2<\/jats:sup>( log n)<jats:sup>O(1\/\u220a<jats:sup>2<\/jats:sup>)<\/jats:sup>) time to compute a (1+\u220a)-approximation with probability \u2265l\/2, and can be derandomized with an additional factor of O(n<jats:sup>2<\/jats:sup>). <\/jats:p>","DOI":"10.1142\/s0218195904001342","type":"journal-article","created":{"date-parts":[[2004,7,2]],"date-time":"2004-07-02T07:18:18Z","timestamp":1088752698000},"page":"19-40","source":"Crossref","is-referenced-by-count":0,"title":["TRAVELING SALESMAN PROBLEM OF SEGMENTS"],"prefix":"10.1142","volume":"14","author":[{"given":"JINHUI","family":"XU","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ZHIYONG","family":"LIN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YANG","family":"YANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RONALD","family":"BEREZNEY","sequence":"additional","affiliation":[{"name":"Department of Biological Sciences,  State University of New York at Buffalo, Buffalo, NY 14260, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"rf7","volume":"42","author":"Berezney R.","journal-title":"Adv. Enzyme Regul."},{"key":"rf8","first-page":"1","volume":"162","author":"Berezney R.","journal-title":"Int. Rev. Cytol."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011497227406"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.387"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80121-5"},{"key":"rf23","volume-title":"The Traveling Salesman Problem","author":"Lawler E. L.","year":"1985"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.2.206"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1109\/70.265920"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195904001342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:20:12Z","timestamp":1565176812000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195904001342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,4]]},"references-count":13,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,4]]}},"alternative-id":["10.1142\/S0218195904001342"],"URL":"https:\/\/doi.org\/10.1142\/s0218195904001342","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,4]]}}}