Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The salesman’s improved paths through forests
Sebő A., Zuylen A. Journal of the ACM66 (4):1-16,2019.Type:Article
Date Reviewed: Sep 19 2019

Given a set of cities and a function that gives the cost of traveling from one city to another, the traveling salesman problem (TSP) determines a circuit of minimal cost that 1) starts and ends in the same city and 2) passes through each city only once. A cost function that satisfies the triangle inequality is called a metric, and the corresponding TSP is called the metric TSP. A slight generalization is the metric s--t path TSP in which “the goal is to find a Hamiltonian path from s to t of minimum cost.”

An approximation algorithm for an NP-hard problem such as TSP and its variants gives, in polynomial time, a solution that lies within some predefined multiplicative factor of an optimal solution. It is shown “that an {s--t}-tour of cost at most 1.5 times the optimum can be found in polynomial time.” However, it is an open problem whether this bound can be replaced by 1.5 OPTLP, where OPTLP is the optimum cost for the subtour elimination linear program (LP) in which every city is entered and exited exactly once and every subset of cities is entered and exited at least once.

In this paper, the authors present a “strongly polynomial-time algorithm” with a cost less than 1.53 times the optimum of the subtour elimination LP for the metric s--t path TSP. The results, initially presented at the IEEE 57th Annual Symposium on Foundation of Computer Science (FOCS), held in 2016, will be of interest to students and researchers studying approximation algorithms.

Reviewer:  D. Bollman Review #: CR146698 (1911-0396)
Bookmark and Share
 
General (G.0 )
 
 
Graph Theory (G.2.2 )
 
 
Discrete Mathematics (G.2 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date

Type: Journal
Feb 1 1986
Science, computers, and people: from the tree of mathematics
Ulam S., Birkhäuser Boston Inc., Cambridge, MA, 1986. Type: Book (9789780817632762)
May 1 1988
Computer science: a mathematical introduction
Lew A., Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780131642522)
Jul 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy