Re:Shortest-possible walking tour to 81,998 bars in South Korea
by alexchamberlain on Thursday April 24, 2025 @02:19AM
(#43779793)
Is the solver guaranteed not to land in a local minima/maxima?
[ Parent
| on HN ]
Re:Shortest-possible walking tour to 81,998 bars in South Korea
by moralestapia on Thursday April 24, 2025 @03:06AM
(#43779988)
(I don't know)
But I would guess the answer is "no".
If you can prove, as they claim, that you have an algorithm that gives you the optimal solution (aside from the obvious, brute-forced one), you might be one stone throw away to make an argument for some P == NP, that would be HUGE.
But it seems that some people get offended when you tell them their perpetual motion machines are not real.
Re:Shortest-possible walking tour to 81,998 bars in South Korea
by unnah on Thursday April 24, 2025 @09:04AM
(#43782219)
The branch-and-bound algorithm does provide a proven optimal solution. This does not mean that P=NP because the size of the proof is not bounded by a polynomial in the input size, and neither is the algorithm runtime. Also, Euclidean TSP is known to be easier than TSP on arbitrary graphs: there are polynomial-time approximation schemes that can produce solutions with an (1+epsilon) factor of the optimum in polynomial time, for any value of epsilon. Thus it is not surprising that a proof of full optimality can be constructed for some instances.
Re:Shortest-possible walking tour to 81,998 bars in South Korea
by inasio on Thursday April 24, 2025 @12:57PM
(#43784920)
The solver generates a relaxed lower bound that indicates how far they could be from the global optimal solution. The moment that the lower bound improves enough to match a path they can guarantee that it's the global optimum