But that presumably doesn't handle the relative motion of the stars, which makes the problem even trickier, since the distances will change as you travel, no? Or is my astronomy off base here?
I think your astronomy skills are correct, but if we have to worry about actual travel then you would also have to consider things like fuel capacity, refuel opportunities, the fact that you probably don't want to actually fly through a star but around it, etc.
I think it's still valid to have a distinction between travel logistics and having a route that's at least theoretically possible. I suppose what they've calculated would work with a star gate like system, but then I'm not sure what the point of having minimal distance would be.
Isn't the flying around problem just "e" since it is so many orders of magnitude less than the distance between stars that for this calculation it is irrelevant anyway?
Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).
So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).
The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.
Iirc the (probably simplified) LKH heuristic they used:
For each iteration:
apply some randomisation
starting at each place
cut the path in 2..n places
reconnect in the most optimal way
if the new tour is the new best, save
LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)
By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)
It's strange that they don't mention the total distance. I understand that the point-to-point travel time is what they're solving for, but it would be interesting to know what the actual distance of travel was, if for no other reason than calculating caloric burn. But then you could also see how much it deviated from the shortest-distance path.
They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.
I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.
> A culture of hanging out and drinking requires walkable urbanism.
I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.
You didn't have to plan to get walkable urbanism before cars. It just happened because everyone needed a pub, store, school, etc. within walking distance.
Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.
A minimum amount of parking spots per patron capacity. So a bar with 60 people capacity must have 15 parking spaces. [0]
Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]
The idea of a bar (ie a place people go to get drunk) with a dedicated parking lot strikes me as particularly bad for road safety. I'm baffled that this is not only encouraged, but mandated.
How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?
Yeah but I mean, if everybody goes to the pub by car, does it mean everybody brings a designated driver? Or is this one of those things where everybody drives drunk but pretends nobody does?
82k places in Korea include any restaurant or joint or karaoke with a license to serve alcohol. Personally I would not care to call 80% of them "bar".
So in Ohio probably everything with class C and D license. How many is not public but probably many times more than 4k.
Many actual street level bona fide bars in Seoul (which has half of all the people of the entire country and the most bars by far) are tiny rooms that fit a few people each. But you always have a "bar street" with 50 of those next to each other.
Many countries have much more used “public” spaces, and people spend much more time in them, together.
The idea of driving home to the suburbs and locking yourself into your private home is very North American.
I just got back from10 months across Europe. The number of people in public places eating, chatting and just spending time (no simply going somewhere) makes LA or Chicago look like a ghost town.
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. :)
"Bar" doesn't mean the same thing in every country. In Spain although a bar serves alcohol of all kinds it is also where one eats breakfast and lunch and gets a coffee. They are indispensable social centers and even a tiny town of 150 has one.
After living there for about four years, my mind goes immediately to soju. Not sure if there is a connection, but that’s something I might deep dive with an LLM today.
reminds me of a question they used to ask in the Irish army back in the 60s. My Dad told me this. "How do you get from Bachelor's Walk to Collins Barracks without passing a bar?". People would spend hours and days working on the answer. In the end, the answer was "Go in to every one".
I'm impressed they found a dataset this hard, but not much harder. It's a delicate balance between beating the last Traveling Salesman hiscore (Netherlands), and never finishing your compute
In the "computations" page[1], the table lists the Netherlands computation as costing 97 CPU years with 6 months of elapsed time, while the Korean bars costs 44 years of CPU time and 3 months of elapsed time. I can't tell if the two problems were solved using the same hardware.
Branch-and-bound is an algorithm "from the book" to me. Fundamentally very simple, provided you view the LP solver as a black box, but incredibly useful.
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.
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/.
I zoomed in on the map and discovered at least one shortcut where one could have saved a few seconds, now is that proof enough that the solution is not optimal? :P
Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.
There was a man who documented his travel to every country in the world. Not long before he was finished, South Sudan gained independence and he had to take a special trip there to complete his journey, which apparently had already completed all the other countries in Africa long ago.
>Our computation produced a tour together with a proof that it is a shortest-possible route [...]
Proof nowhere to be found.
Waterloo-ers are nice people but I see an increasing trend of them just lying to get some cred. Come on guys, you don't have to follow the valley model that much.
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.
People really really really need to take some time to understand the concept of "burden of proof", so they can't stop making fools of themselves in public.
The solution was found in a few days by the LKH TSP heuristic solver. They spent months (and decades of CPU time) using well-known techniques to bound the specific problem and prove that this was an optimal solution. It’s not something that you can synthesize to a page. They are literally announcing that they verified the heuristic-derived solution.
Consider it like any science, where folks can make shit up. But you can just run the bounding algorithms yourself, or prove they are incorrect.
>But you can just run the bounding algorithms yourself, or prove they are incorrect.
People really really really need to take some time to understand the concept of "burden of proof", so they can't stop making fools of themselves in public x2.
The proof here is essentially the execution log of the bounding program. I imagine that this would be TB, PB or beyond. Not every proof is some clever paper, some are just brute force. Like proving a number is prime, or calculating the Nth digit of Pi. A paper doesn’t always make sense, but you can still announce what you’ve done (and maybe you get a paper with algorithmic details, but it’s not a proof for specific the instance).
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.
You could still save the branch-and-bound tree, the LP problems solved at the tree nodes, the derivations of the LP cutting planes, and the LP solutions that together constitute the proof. Then you could in principle create an independent verifier for the branch-and-bound tree and cutting plane derivations, which could potentially be much more straightforward and simple code than the entire Concorde TSP solver, and wouldn't have so high performance requirements.
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.