We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
One-Way Salesman Finds Fast Path Home
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    Abstractions blog

    One-Way Salesman Finds Fast Path Home

    By Mark Kim-Mulgrew

    October 5, 2017

    The real-world version of the famous “traveling salesman problem” finally gets a good-enough solution.
    Comment
    Read Later
    Directed salesman problem

    Lucy Reading-Ikkanda/Quanta Magazine; Photo T.Dallas

    By Mark Kim-Mulgrew

    Contributing Writer


    October 5, 2017


    View PDF/Print Mode
    Abstractions blogalgorithmscomputational complexitycomputer sciencetraveling salesperson problemAll topics

    Introduction

    A salesman has to visit every major city in the U.S. What is the cheapest way to hit them all exactly once and then return to the headquarters? The computation of the single best answer for what is known as the traveling salesman problem is famously infeasible. Nevertheless, computer scientists have long known how to find a pretty good route — one that incurs no more than 1.5 times the optimal cost.

    The traveling salesman problem assumes that a trip between any two cities will cost the same going in either direction. But that’s often not the case. For example, perhaps a flight from Chicago to Denver is cheaper (or takes less time) than the flight from Denver to Chicago. Finding the optimal flight path under these conditions — known as the asymmetric traveling salesman problem — is also computationally infeasible. But unlike when solving the plain vanilla traveling salesman problem, researchers didn’t know how to find a near-optimal route for a trip to a large number of cities. That is, until last month, when three computer scientists announced that they had devised an approximation algorithm that remains efficient in all cases.

    Why is the asymmetric traveling salesman problem so hard? In short, when routes are more expensive in one direction than they are in the other, there are many more routes to consider. The added difficulty meant that, until now, all algorithms for solving the asymmetric traveling salesman problem would either take too long or result in unusable routes. The new algorithm thus “solves a long-standing open problem and is a breakthrough of the first order,” wrote Ken Regan of the University at Buffalo and Dick Lipton of Georgia Tech on Gödel’s Lost Letter and P=NP, a blog on contemporary algorithms research.

    “The first time I thought about the problem was during my Ph.D. in 2008,” said Ola Svensson, one of the three authors of the new paper. After seven years of hacking away at the problem, Svensson came up with a solution for a simpler problem of lumping cities together into groups and visiting at least one city from each group.

    Svensson then enlisted Jakub Tarnawski and László Végh, his coauthors, to help him develop a new algorithm that repeatedly forms smaller subgroups within the groups of cities until it identifies cheap routes within each group. The routes within the groups are then patched together, using Svensson’s previous research, to construct a full route. While previous attempts at solving the asymmetric traveling salesman problem used similar approaches, none of them were successful at locating the groups of cheap routes that can be patched together.

    While the paper has not been peer reviewed yet, Regan said it has a good chance of withstanding the computer science community’s scrutiny. “The ideas in the proofs are very clear,” Regan said. “There is one potential sensitive [technical] point … [but] very solid, very promising, well structured, and well broken-out.”

    Svensson said he and his coauthors planned to submit their paper to an upcoming conference — the 50th annual Symposium on the Theory of Computing — for formal peer-reviewing.

    This article was reprinted in Spanish at Investigacionyciencia.es.

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    By Mark Kim-Mulgrew

    Contributing Writer


    October 5, 2017


    View PDF/Print Mode
    Abstractions blogalgorithmscomputational complexitycomputer sciencetraveling salesperson problemAll topics
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    Cryo-electron microscopy

    Next article

    Supercool Protein Imaging Gets the Nobel Prize
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023