Shortest-possible walking tour to 81,998 bars in South Korea

Re:Shortest-possible walking tour to 81,998 bars in South Korea by rurban on Thursday April 24, 2025 @12:52AM (#43779346)

So NP is like P again. I learned in school 13 is the max and one of my algebra professors advanced it to 15 (in the 80ies). Then came 20, then came 20.000, this is 80k with proof, and at the World TSP page we see the record was 1m.

http://webhotel4.ruc.dk/~keld/research/LKH/

The biggest proven optimum is for 3178031 right now.

This should be really done with CUDA, not plain C, btw.

[ Parent | on HN ]

Re:Shortest-possible walking tour to 81,998 bars in South Korea by eduardosalaz on Thursday April 24, 2025 @01:24AM (#43779511)

There is tons of work to do on running optimization algorithms in GPU. In its current form, Branch and Bound and Cutting Planes do not gain an advantage if implemented in CUDA. There is a new algorithm, PDLP, which is implementable in GPUs but it is still in early stages. For more, see https://blogs.nvidia.com/blog/cuopt-open-source/.

[ Parent | on HN ]

Re:Shortest-possible walking tour to 81,998 bars in South Korea by JohnKemeny on Thursday April 24, 2025 @01:29AM (#43779544)

The thing is that Euclidean TSP needs a lot of data to encode hard instances.

N=15 was even considered solved in the 60s, and N=20 has never been considered large instances, especially not of Euclidean TSP.

I cannot see how anyone could say 13 is the max: you need 100k memory slots and 1M comparisons. This has been trivial for quite some time.

[ Parent | on HN ]

Re:Shortest-possible walking tour to 81,998 bars in South Korea by rurban on Thursday April 24, 2025 @02:17AM (#43779781)

Yeah, I probably mixed it up with the Hamiltonian Path problem. It was a long time ago

[ Parent | on HN ]

Re:Shortest-possible walking tour to 81,998 bars in South Korea by moralestapia on Thursday April 24, 2025 @03:10AM (#43780012)

>80k with proof

Post proof.

[ Parent | on HN ]