19 ms·
Computer Scientists Break Traveling Salesperson Record
- growlist 6y agoWhilst I'm thrilled that the monstrous partriachal injustice of the name of a mathematical problem including 'man' rather than 'person' has been annihilated, I'm also concerned about the extra co2 emissions generated by the data transfer associated with those three extra letters.
- war1025 6y agoI was inclined to comment on the ridiculousness of insisting on using "salesperson" which is a real mouthful to say a hundred times over as is done in the article. But I figured that was just me being cranky and objectionable lately.
- hnracer 6y agoIt's not just you being cranky lately, it is indeed ridiculous.
- happytoexplain 6y agoFrom my point of view, having negative emotions about this at all seems "ridiculous", much more describing it as "a mouthful", and framing it as their having "insisted" on doing something, rather than simply having done it.
- mmm_grayons 6y agoWell, the generally-accepted term has been "salesman" for over a hundred years. Whether or not you approve, it's definitely a conscious choice. As an aside, can someone explain why a generic "-man" suffix is taken to indicate only the masculine by some people? It's no different than using the masculine for indefinite gender, so why the objections?
- JoeAltmaier 6y agoWell, because it says "man" and that means a male. Never mind its from the German where 'man' meant 'person'; today in English we are where we are. And 'a hundred years' is not much of a defense. Women couldn't sign a mortgage in the US in the 70's. I imagine folks defended that too - "Its the way we've always done it."
- vkowalski 6y agoHupersons, personkind etc. This is not where we are in English.
- polynomial 6y agoWe'll get there! Baby steps...
- 0-_-0 6y agoA small step for person, a giant leap for personkind!
- thursday0987 6y ago> Women couldn't sign a mortgage in the US in the 70's. yeah you're going to need to provide a source for such a ridiculous claim. My grandmother has owned her house for much longer than that. * edit: all you downvoters need to look at the claim being made instead of bringing up different issues. credit cards are not mortgages. "couldn't sign" is not the same as "needed a cosigner" or "discounted rates". the original claim implies that women could not own houses through a bank loan, which is very much false.
- JoeAltmaier 6y agoSure, own one by inheiriting or paying outright. Its the credit issue that prevented borrowing to buy one. Our recently deceased Supreme Court Justice was instrumental in securing that right. Here's a brief history for the Google-challenged: https://www.directlendingsolutions.com/women_and_credit.htm https://www.directlendingsolutions.com/women_and_credit.htm
- read_if_gay_ 6y agoIf you think it’s ridiculous to get irritated by “salesperson” then it should also be ridiculous to get irritated by “salesman”.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- phkahler 6y ago>> which is a real mouthful to say a hundred times over as is done in the article. It's often reduced to TSP.
- happytoexplain 6y agoWhy reframe something so harmless with such wild exaggeration and sarcasm?
- renewiltord 6y agoI literally didn't even notice until these guys said it. Can't imagine how people care so much about trivialities like this.
- dang 6y agoWe've banned this account for taking HN threads repeatedly into gender flamewar, and other kinds of flamewar, and ignoring our many requests to stop—such as this explanation from just two weeks ago: https://news.ycombinator.com/item?id=24569144 https://news.ycombinator.com/item?id=24569144. Vandalizing HN like this is not cool.
- jk700 6y agoExcept maybe for current comment (not really, HN just has more replies on anything these days), nothing actually turned into flamewars, most out of his few "flamewar" comments over many months barely had any replies at all and were just flagged. It seems you are labeling them as flamewar just so you could justify banning him. Possibly because he expressed opinions you consider "politically incorrect" today and you want to suppress such opinions on HN. Also you can't claim he ignored your many requests to stop, because you never made a single request to stop what can be interpreted the same way by both of you, he probably thought he followed them. Again, you were using this as manufactured justification to ban him.
- Nuzzerino 6y ago>Also you can't claim he ignored your many requests to stop, because you never made a single request to stop what can be interpreted the same way by both of you, he probably thought he followed them. Again, you were using this as manufactured justification to ban him. One could attempt to make this same argument over virtually any ban ever. There doesn't need to be a reason in my opinion. HN has never allowed freedom to express any opinion you want. A pattern of unpopular opinions tends to result in an automatic hellban, for example.
- jk700 6y agoNo, dang is purposely vague in all of his warnings, as if he wants to make sure people won't be able to follow them and it will be up to him to decide whether they did or didn't. If somehow he slips and they manage to do it, he will rephrase them next time, make them more vague and more subjective to make sure they don't. Like I saw a warning he gave someone to stop creating new accounts every couple of comments, but then in other warnings he stretched his definition farther and farther to include more comments and more time.
- elygre 6y agoHow the heck did he do that during covid? Did he break all travel restrictions?
- gibolt 6y agoVacuum salesman used his vacuum to reduce friction
- deleted 6y ago[deleted]
- blululu 6y agoLockdown -> O(1) traveling salesperson solution. I think constant runtime is technically not polynomial hard... But seriously this is very cool. Glad to see progress in mathematics.
- belinder 6y agoI'm glad too but it's difficult for me to imagine the improvement when it's > 0.2 billionth of a trillionth of a trillionth of a percent
- Tyr42 6y agoOh man, it's actually a real improvement! I was afraid it was more pop sci, but not this is pretty cool. I think this is the paper? https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409
- ebg13 6y agoHeh. For some definitions of "real". > they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
- np_tedious 6y agoLooks like a real number to me
- deleted 6y ago[deleted]
- DudeInBasement 6y agoMy double won't notice the difference
- deleted 6y ago[deleted]
- tuxone 6y agoYea but just rational
- mjn 6y agoThe paper is really nicely written: https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409 It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified cases. An example is on p. 19, section 3.1, "Ideas underlying proof of Theorem 3.1".
- pantsforbirds 6y ago"A (Slightly) Improved Approximation Algorithm for Metric TSP" is a pretty funny headline.
- MrXOR 6y agoNathan Klein's talk is also nice: https://www.youtube.com/watch?v=TE6puoxv2wY https://www.youtube.com/watch?v=TE6puoxv2wY
- mensetmanusman 6y agoIf we are renaming things from the past to quell the moderns, it should be renamed Traveling Seller since it rolls off the tongue so much better.
- rcoveson 6y agoNow do longshoreman. :)
- Igelau 6y ago1974 just called to clarify https://ieeexplore.ieee.org/document/4569756 https://ieeexplore.ieee.org/document/4569756
- mensetmanusman 6y agoThis one from the 50’s has a few thousands citations: “Solution of a Large-Scale Traveling-Salesman Problem“ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.606.2752&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.606... Currently Google scholar shows ‘salesman’ with an order of magnitude more references than ‘salesperson’ My only point is that if we are going to fork the reference, we should use something that is easier to say. (I honestly don’t care if we fork the reference :) ).
- Igelau 6y agoInteresting. I find 'salesperson' pretty easy to pronounce, and it has the advantage of not being homonymous with "cellar". Mileage may vary for your dialect and accent.
- X6S1x6Okd1st 6y agoFor people that want to argue about salesperson vs salesman you may be comforted to know that you don't need to, it's already being done! https://en.wikipedia.org/wiki/Talk:Travelling_salesman_problem#Salesperson https://en.wikipedia.org/wiki/Talk:Travelling_salesman_probl...
- interestica 6y agoWhat of the people wanting to argue about the two different (correct) spellings of 'travelling/traveling' used in this thread?
- SQueeeeeL 6y agoThat was just them describing random internal wikipedia things with a debate about google scholar. There wasn't really a debate there...
- X6S1x6Okd1st 6y agoIf you search the page for "salesperson" there are other debates.
- gotoeleven 6y agoIt reminds me of when at some point in the 90s everyone decided to stick it to jesus by changing B.C. to B.C.E.
- rsynnott 6y ago> In 1856, Rabbi and historian Morris Jacob Raphall used the abbreviations CE and BCE in his book Post-Biblical History of The Jews Older than you’d think.
- kats 6y ago> proved that an algorithm devised a decade ago beats Christofides’ 50% factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. That is 0.0000000000000000000000000000000002% better than the existing solution.
- blackbear_ 6y agoAre you missing two zeros or am I counting incorrectly? The paper claims an improvement of 10-36 or smaller
- triclops200 6y agoPercent moves two zeros over factor
- morcheeba 6y agoSo much less than the 0.01% of the variation in identical computers due to 100ppm crystal variation. Also less than the 0.0001% variation due to the temperature in the room changing 1 degree.
- jobigoud 6y agoWonder if it's less than the probability of getting hit by a cosmic ray flipping a bit somewhere in the implementation and changing the result.
- bitcharmer 6y agoThis is very interesting. Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
- morcheeba 6y agoXEONs use a 100MHz referenced called "BCLK" and scale this up to the different frequencies it needs internally (core, dram, pci, etc.). Typically this info is found in the datasheet, but only the DC parameters (voltage min/max) etc were found in the first datasheet I found. Timing is so important that often processor manufacturers will have an apnote discussing it in detail, often with suggested parts and circuit layouts. https://www.intel.com/content/www/us/en/products/docs/processors/xeon/2nd-gen-xeon-scalable-datasheet-vol-1.html https://www.intel.com/content/www/us/en/products/docs/proces...
- molticrystal 6y agoWhile it is wonderful they are getting closer to solving it, if your problem is a simple and practical you can try some alternative algorithms. For fun, I used pytspsa [0] which uses the simulated annealing method to solve the TSP and applied it to BOTW. Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1] I combined it with a Breath of the Wild waypoint generator [2] to make my way around the map [3] in a mostly optimal fashion for my trip about Hyrule. If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved. [0] https://github.com/ildoonet/simulated-annealing-for-tsp https://github.com/ildoonet/simulated-annealing-for-tsp [1] https://en.wikipedia.org/wiki/Simulated_annealing https://en.wikipedia.org/wiki/Simulated_annealing [2] https://github.com/MrCheeze/botw-waypoint-map https://github.com/MrCheeze/botw-waypoint-map [3] https://user-images.githubusercontent.com/2829875/28661246-0b631e52-7284-11e7-8bd5-71998c75b11b.png https://user-images.githubusercontent.com/2829875/28661246-0...
- jokethrowaway 6y agoThis is great, thanks for sharing! I had good results with genetic algorithms as well.
- mjn 6y agoThere are also TSP-specific heuristics that work well in practice on a lot of large instances, often finding the optimal solution pretty quickly (but with no guarantees of optimality). The first I believe was the Lin-Kernighan heuristic from 1973 (the same Kernighan as the 'K' in K&R C, incidentally). There are fast implementations of some modern improved versions, e.g.: http://akira.ruc.dk/~keld/research/LKH/ http://akira.ruc.dk/~keld/research/LKH/
- IncRnd 6y agoI coded a version of SA for TSP in the early 90s. I iterated until the probability of a hardware error was greater than having a sub-optimal solution. It took just a couple of seconds, and that speed was due to visually displaying the algorithm as it executed.
- LeoPanthera 6y agoThis is kind of a hijack, but it's at least related: Are there any websites/apps that can approximate a solution for road destinations in the real world? For example, given a list of cities, an approximate solution on actual roads to visit all of them once?
- Brushfire 6y agohttps://routific.com/ https://routific.com/
- LeoPanthera 6y agoYeah this is not what I meant at all. I'm looking for something that me, a normal boring non-tech end user can use.
- jonbaer 6y agoOR-Tools, https://developers.google.com/optimization/routing/tsp https://developers.google.com/optimization/routing/tsp
- LeoPanthera 6y agoSo I guess if you're not a developer, the answer is "no". Someone should make a front end for this.
- jonbaer 6y agoWhile not entirely obvious on Google Maps you can add multiple stops and reorder them for fastest route (including traffic which you might not be able to get w/ OR-Tools), https://support.google.com/maps/answer/144339 https://support.google.com/maps/answer/144339
- fromaj 6y agoI'd say this is pretty decent but it's not a proper TSP app, since it expects the first and last points as fixed but has the option to change the order of the other stops https://www.mapquest.com/routeplanner https://www.mapquest.com/routeplanner
- fmeyer 6y ago“The algorithm we study is very similar, except we choose a random spanning tree based on the standard linear programming relaxation of TSP.” That’s so subtle to suggest but incredible hard to prove https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409
- teknopurge 6y agoIt looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown and effort though - very useful.
- MaxBarraclough 6y ago> It's novel, but not reliable. Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets. If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.) As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle. (Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)
- FartyMcFarter 6y ago> It's an NP-complete problem Finding the optimal solution is NP-complete, but approximations are not necessarily so: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Complexity_of_approximation https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co...
- MaxBarraclough 6y agoRight, I should have made that point more clear. The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems. Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.
- MaxBarraclough 6y ago> able to subtract 0.2 billionth of a trillionth of a trillionth of a percent ... > “This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s I love this. Oh to be a theoretician. Here's hoping for a flood of further improvements.
- pkaye 6y agoMeanwhile in an agile dev team.... "can you optimize it in the next sprint?"
- booleandilemma 6y ago“so you don’t have anything to demo, then?”
- bigiain 6y agoInterestingly, I demoed and shipped a wayfinding solution for a mobile app earlier this year, where I just brute forced the shortest paths between all pairs ~200 "intersections" in the area of interest for this event, and just stored the answers in a KV store based on the intersections (then does some cheesy last 20m stuff to route you to and from the nearest intersections to your location and destination). In a limited-enough space (like an event), this works out just fine. I'm glad I'm not the guy who needs to solve GoogleMap's routing problems though. I wonder if they have a huge BigTable store of every street intersection pair on the planet and a recalculated best route between them? I _hope_ they do something smarter than my "works in my constrained requirements space" brute-force hack...
- exikyut 6y agoWhen my local public transport (bus+train) did a major-ish route overhaul, routing directions on Maps glitched out for a couple days and showed large "black spots" (maybe 5-15mi in size?) where regions of generally accurate/useful routing were slapstuck together with large straight lines that cut diagonally through backyards, houses, major highways, etc (and sadly didn't account for runway room so weren't even flyable). So in a scenario where you were zoomed out enough to see 2-3 towns, you'd get a complex route shape in one part of the map, another complex route shape in another part of the map, then one single "nope I can't do this" giant line connecting the two regions. The giant line often connected to the complex shapes at awkward angles, eg 60-70°. Unfortunately IIRC most of the screenshots I took show my actual address/immediate surrounding area etc, so they'd be fairly heavily censored. If anyone [is actually reading this and] is especially interested, I can try braving my scary not-organized screenshot archive and try and find them.
- codezero 6y agoVery tangential, I was a physics major, and learned about Traveling Salesperson when in college at UCSD - I looked it up in the library and there was like, an entire hallway of books/research on this problem and it blew my mind. It really put into perspective how much work had gone into that single problem. I think the shelf was larger than the solar physics papers on file in a nearby area.
- ofou 6y agoSo, how many kms would be to visit the 1,904,711-city instance throughout the world?[1] I'm already packing. [1]: http://www.math.uwaterloo.ca/tsp/world/ http://www.math.uwaterloo.ca/tsp/world/
- sigmaprimus 6y agoI was just thinking on the TSP the other night, would a practical application of this problem(and solution) be to use it in processor circuit layout and trace routing? Then using the improved processor to solve the problem again?
- ellis-bell 6y agoprobably circuit satisfiability and related hard problems are all reducible to each other
- lamchob 6y agoMaybe, but a real challenge of circuit layout and routing is that you want to generate (mostly) planar graphs, since your options for intersecting connection lines are limited and expensive. For the TSP, this does not really matter since the problem is more abstract.
- sigmaprimus 6y agoInteresting point, TBH I had never considered applying the TSP to any more than two dimensions, as it becomes exponentially more difficult with each node added even within the same plane. I'm not even sure if adding more dimensions would make it more difficult or not but You have me thinking on that now, so thank You.
- vlovich123 6y agoOr use deep learning to generate solutions 2 orders of magnitude faster with some minor accuracy loss. https://arxiv.org/pdf/1905.05567.pdf https://arxiv.org/pdf/1905.05567.pdf
- bnegreve 6y agoApparently, heuristics are still better than DL-based solutions for the TSP From the paper you linked: heuristics based solutions are still superior to deep learning based solvers regarding accuracy and execution time for larger problem sizes.
- ladberg 6y agoPretty much any decent off the shelf algorithm is faster than deep learning if you allow it the same accuracy loss.