TY - JOUR
T1 - The TSP and the sum of its marginal values
AU - Dror, Moshe
AU - Lee, Yusin
AU - Orlin, James B.
AU - Polishchuk, Valentin
N1 - Funding Information:
*Preliminary version1 appeared in the abstracts of the 14th Annual Fall Workshop on Computational Geometry, November 2004. tWork done while M. Dror was visiting Operations Research Center, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA JNow at Department of Civil Engineering, National Cheng Kung University Tainan, Taiwan §This work was supported in part by Office of Naval Research grant ONR N00014-98-1-0317. ^V. Polishchuk is partially supported by the National Science Foundation (CCF-0431030), NASA Ames (NAG2-1620), and a grant from Metron Aviation.
PY - 2006/8
Y1 - 2006/8
N2 - This paper introduces a new notion related to the traveling salesperson problem (TSP) - 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 ∈ 7 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.
AB - This paper introduces a new notion related to the traveling salesperson problem (TSP) - 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 ∈ 7 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.
UR - http://www.scopus.com/inward/record.url?scp=33746888202&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746888202&partnerID=8YFLogxK
U2 - 10.1142/S0218195906002063
DO - 10.1142/S0218195906002063
M3 - Article
AN - SCOPUS:33746888202
SN - 0218-1959
VL - 16
SP - 333
EP - 343
JO - International Journal of Computational Geometry and Applications
JF - International Journal of Computational Geometry and Applications
IS - 4
ER -