The TSP and the sum of its marginal values

Moshe Dror, Yusin Lee, James B. Orlin, Valentin Polishchuk

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)333-343
Number of pages11
JournalInternational Journal of Computational Geometry and Applications
Issue number4
StatePublished - Aug 2006
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'The TSP and the sum of its marginal values'. Together they form a unique fingerprint.

Cite this