News for hackers. Stuff that matters.
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?
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