Stories
Slash Boxes
Comments

SoylentNews is people

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

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

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by turgid on Tuesday October 10 2017, @10:37AM (3 children)

    by turgid (4318) Subscriber Badge on Tuesday October 10 2017, @10:37AM (#579719) Journal

    I usually find I get home fastest when I'm on my beer scooter.

    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 1, Touché) by Anonymous Coward on Tuesday October 10 2017, @12:02PM (2 children)

    by Anonymous Coward on Tuesday October 10 2017, @12:02PM (#579740)

    But, how many pubs do you stop at on the way home? And do you visit them in an optimal sequence??