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

• Re:Approximation Re:Approximation (Score: 2) by TheRaven on Tuesday October 10 2017, @10:38AM (1 child)

  by TheRaven (270) on Tuesday October 10 2017, @10:38AM (#579720) Journal

  To add to that: this is true in the specific case of the travelling salesman problem. There are a number of algorithms that give good solutions in varying complexity classes. I seem to recall (though, checking Wikipedia, it looks as if I may have made this up) that the travelling salesman problem is much easier to solve if you place some constraints on the structure of your graph that happen to map quite nicely to the kinds of roads that people build, making the practical version a lot easier in the majority of cases than the graph theoretic problem.

  --
  sudo mod me up

  Parent

  Starting Score:	1		point
  Karma-Bonus Modifier		+1
  Total Score:		2

• Re:Approximation (Score: 0) by Anonymous Coward on Thursday October 12 2017, @07:07PM

  by Anonymous Coward on Thursday October 12 2017, @07:07PM (#581293)

  > the travelling salesman problem is much easier to solve if you place some constraints

  Goodness me yes! It's an absolutely tractable problem under lots of conditions. I forget what boundaries are big-O (complexity) better and which are just empirically useful, but some which have been investigated include: directed graphs, trees, planar graphs, maximum degree (# of edges/node), bounded edge length...

  There's some pretty amazing properties where, like including or excluding '0' from the domain of a function, suddenly the problem can have a vastly different meaning.

  Any graph maths or CS types around here able to link to an understandable overview of modified travelling salesman?

  Parent