Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

math.uwaterloo.ca

Post reply on HN
Print view View original

41–50 of 147 posts

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

#41

Post by yard2010 »

kijin wrote: post #23
notesinthefield wrote: post #8

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

Looks like they got their hands on a dataset of every restaurant that is licensed to serve alcohol -- or at least a decent subset of such restaurants, filtered by menu or whatever. I checked a few dots near where I live and they're all fried chicken joints. Yeah, we do love chimaek around here. :)

In korea after a certain hour every restaurant, karaoke, PCBang, and hotteok parlor is basically a bar :)

God I miss this place so much <3

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

#42

Post by eduardosalaz »

rurban wrote: post #36

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.

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/.

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

#43

Post by JohnKemeny »

rurban wrote: post #36

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.

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.

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

#45

Post by codemac »

lifthrasiir wrote: post #16
notesinthefield wrote: post #8

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

That country has a population of 52 million, i.e. about 5 times Ohio.

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people.

[0]: https://rentechdigital.com/smartscraper/business-report-deta...

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

#46

Post by aktuel »

codemac wrote: post #45
lifthrasiir wrote: post #16

Earlier quoted context omitted.

That country has a population of 52 million, i.e. about 5 times Ohio.

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people. [0]: https://rentechdigital.com/smartscraper/business-report-deta...

Ohioans love "big bars".

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

#48

Post by moralestapia »

inasio wrote: post #25
moralestapia wrote: post #17

[flagged]

Not sure what you expected to get. The Concorde TSP solver is an exact solver that uses branch and bound search, it will return either a solution with a specified bound or the optimal bound. They provide the dataset and the solution they found (and I believe their solver is open source), if you don't believe them you can go ahead and find a better tour.

[flagged]

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

#49

Post by rurban »

JohnKemeny wrote: post #43
rurban wrote: post #36

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.

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.

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

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

#50

Post by alexchamberlain »

inasio wrote: post #32
7e wrote: post #26

Earlier quoted context omitted.

I also expected to get an actual proof.

Proof in this case is that the upper bound and the lower bound of the solver converged. This is not like a SAT solver where the solution itself can be trivially evaluated to verify the solution, it requires trusting that the solver does what it's supposed to be doing, similar to what happens when you solve a MILP with Gurobi or CPLEX.

Is the solver guaranteed not to land in a local minima/maxima?
Post reply on HN