Hacker News new | past | comments | ask | show | jobs | submit login

> It's an approximation algorithm.

Clear. Nice. Thanks.

In that case, for the Traveling Salesman problem, build a minimum spanning tree and traverse that -- old result.




The 'general' TSP (unless P=NP) does not admit a worst-case constant-factor approximation, at least not on classical machines (we're still working on the quantum PCP theorem).

So while I'm not immediately familiar with the approximation algorithm you're suggesting (unless it is Christofides[1]), it seems unlikely that it would produce a good approximation for the TSP. It might still perform well in the average-case over random instances. I'll admit I haven't delved deeply into that about the TSP, but I don't believe there are currently any favorable results. There are certainly no Overlap Gap Property related results about the TSP. If I wanted to prove something in the average case about the TSP, I'd definitely be starting there.

[1]: If you were thinking about Christofides: Christofides is indeed a 3/2-approximation, but not for the general TSP. Instead, it approximates a problem like the TSP, known as the Metric TSP. The Metric TSP introduces additional symmetries that make it much, much easier to approximate. As such, Christofides is an approximation algorithm for an approximate version of the problem, which I think is pretty neat. If I'm remembering correctly, the inapproximability results for the Metric TSP are rather favorable.


In grad school, wrote a paper as a homework assignment for a course where reviewed a paper on the idea of using a minimium spanning tree for the traveling salesman problem. The paper did have some math addressing how close the idea was to optimality. That was a long time ago, and now don't have the reference or the homework! From a fast search, now there is

https://www.geeksforgeeks.org/approximate-solution-for-trave...

https://en.wikipedia.org/wiki/Minimum_spanning_tree

Am reminded that the nodes to be visited must have distances that obey the triangle inequality, e.g., like a plane.

Then when traversing the tree, when there is no arc in the tree to the next node, just leave the tree and go direct.


I think its more like trying to find the highest mountain in a range of mountains, except there's too much fog so you can't see how high other mountains are compared to the one you're on, so you can't tell if you're on the highest mountain until you've climbed them all.

A lot of the non-quantum heuristical approaches leave you isolated on one of a few mountains (local maxima), because simply climbing back down and hoping to find another peak is computationally expensive and you know it will lead to a lot of suboptimal solutions before finding something hopefully comparable or even better than your highest peak reached so far.




Consider applying for YC's Summer 2025 batch! Applications are open till May 13

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: