{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T19:07:22Z","timestamp":1648926442282},"reference-count":3,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,8]]},"abstract":"<jats:p> This paper introduces a new notion related to the traveling salesperson problem (TSP) \u2014 the notion of the TSP ratio. The TSP ratio of a TSP instance I is the sum of the marginal values of the nodes of I divided by the length of the optimal TSP tour on I, where the marginal value of a node i \u2208 I is the difference between the length of the optimal tour on I and the length of the optimal tour on I\\i. We consider the problem of establishing exact upper and lower bounds on the TSP ratio. To our knowledge, this problem has not been studied previously. <\/jats:p><jats:p> We present a number of cases for which the ratio is never greater than 1. We establish a tight upper bound of 2 on the TSP ratio of any metric TSP. For the TSP on six nodes, we determine the maximum ratio of 1.5 in general, 1.2 for the case of metric TSP, and 10\/9 for the geometric TSP in the L<jats:sub>1<\/jats:sub> metric. We also compute the TSP ratio experimentally for a large number of random TSP instances on small number of points. <\/jats:p>","DOI":"10.1142\/s0218195906002063","type":"journal-article","created":{"date-parts":[[2006,8,7]],"date-time":"2006-08-07T10:44:32Z","timestamp":1154947472000},"page":"333-343","source":"Crossref","is-referenced-by-count":0,"title":["THE TSP AND THE SUM OF ITS MARGINAL VALUES"],"prefix":"10.1142","volume":"16","author":[{"given":"MOSHE","family":"DROR","sequence":"first","affiliation":[{"name":"MIS Department, College of Business and Public Administration, University of Arizona Tucson, Arizona 85721, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YUSIN","family":"LEE","sequence":"additional","affiliation":[{"name":"Operations Research Center, Massachusetts Institute of Technology, 77 Massachusetts Avenue Cambridge, Massachusetts, 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JAMES B.","family":"ORLIN","sequence":"additional","affiliation":[{"name":"Operations Research Center, Massachusetts Institute of Technology, 77 Massachusetts Avenue Cambridge, Massachusetts, 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VALENTIN","family":"POLISHCHUK","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Statistics Department, Stony Brook University, Stony Brook, New York, 11794-3600, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Traveling Salesman Problem and Its Variations","author":"Gutin G.","year":"2002"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90074-0"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906002063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:18Z","timestamp":1565137818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906002063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8]]},"references-count":3,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,8]]}},"alternative-id":["10.1142\/S0218195906002063"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906002063","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,8]]}}}