SoylentNews

One-Way Salesman Finds Fast Path Home

posted by martyb on Tuesday October 10 2017, @07:49AM   
from the problem-of-looking-for-an-asymmetric-traveling-salesman dept.

An Anonymous Coward writes:

The real-world version of the famous traveling salesman problem finally gets a good-enough solution.

From the abstract on arXiv https://arxiv.org/abs/1708.04215 (full article is available):

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

[1] LP == Linear Programming
[2] ATSP == Asymmetric Traveling Salesman Problem

Any Soylentils able to explain what, if any, impact this research has on the class of NP-complete problems?

source:
https://www.quantamagazine.org/one-way-salesman-finds-fast-path-home-20171005/

---

Original Submission

• No real impact on NP-completeness (Score: 5, Informative) by stormwyrm on Tuesday October 10 2017, @08:43AM

  by stormwyrm (717) on Tuesday October 10 2017, @08:43AM (#579699) Journal

  What we have here is a heuristic that they have proved is at most 1.5 times longer than the most optimal route. However, the NP-completeness of the travelling salesman problem is based on the exact solution, the actual shortest path that the travelling salesman could take. There exists a polynomial-time algorithm capable of transforming an instance of any NP-complete problem into any other (polynomial time reduction), so if one can solve any one NP-complete problem in polynomial time, you can solve any other NP-complete problem in polynomial time too. Say, if you had the shortest path for an instance of the travelling salesman problem, you could transform that travelling salesman problem into a Hamiltonian cycle problem (also NP-complete) and your shortest path in the TSP problem would also be reducible to the answer of the Hamiltonian cycle. However, if you had only an approximate answer to the travelling salesman problem, even if it were good enough for practical purposes such as if you actually needed to travel to all those places yourself, it would not provide you with the solution to the equivalent Hamiltonian cycle problem, or any other NP-complete problem you could reduce it to.

  --
  Numquam ponenda est pluralitas sine necessitate.

  Starting Score:	1		point
  Moderation		+3
  Informative=3, Total=3
  Extra 'Informative' Modifier		0
  Karma-Bonus Modifier		+1
  Total Score:		5