This 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?
Computer Scientists Break Traveling Salesperson Record
151–160 of 188 posts
Re: Computer Scientists Break Traveling Salesperson Record
#152> 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.
Is it a probabilistic improvement, like over millions of iterations? It does mention choosing tree paths at random... so couldn't that be an improvement by chance?
No, they don't just random sample the base trees and hope for a better result. Their "actual work" is providing a 80 page proof for their improvement.
Re: Computer Scientists Break Traveling Salesperson Record
#153I 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?
Maybe, 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.
Re: Computer Scientists Break Traveling Salesperson Record
#154Earlier quoted context omitted.
Interestingly, 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 limi…
Route-finding is much simpler than traveling salesperson. The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even hig…
As someone that sees 65 as an overly cautious limit and not precisely born in the US, what do you mean by the effects have worn off?
Re: Computer Scientists Break Traveling Salesperson Record
#155Earlier quoted context omitted.
Lately it feels like agile is where innovation goes to die :(
I agree. It’s sad. Agile principles are awesome, but by the time you run them through many company’s implementations of Scrum or SAFe or (God forbid) Jira, you may as well just do waterfall. I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.
Waterfall is actually agile, if one bothers to read the original paper properly, regardless of its bad name.
Re: Computer Scientists Break Traveling Salesperson Record
#156Earlier quoted context omitted.
Interestingly, 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 limi…
Route-finding is much simpler than traveling salesperson. The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even hig…
We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads.
An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A
Re: Computer Scientists Break Traveling Salesperson Record
#157Earlier quoted context omitted.
Route-finding is much simpler than traveling salesperson. The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even hig…
We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads. An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A
Winding British country lanes aren’t a bug, they’re a feature!
Re: Computer Scientists Break Traveling Salesperson Record
#158Earlier quoted context omitted.
Except 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 wa…
>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…
No, 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.
Re: Computer Scientists Break Traveling Salesperson Record
#159Earlier quoted context omitted.
Except 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 wa…
When someone is routinely dropping lit matches in a dry forest, "he only started one wildfire" is obviously no defense. Anyone who sincerely wanted to follow the rules at https://news.ycombinator.com/newsguidelines.html would be behaving completely differently. Sincere misunderstandings are generally quite easy to clear up. If someone doesn't sincerely want to follow the site guidelines, they shouldn't be posting her…
No one can sincerely follow those rules, because they are too subjective. The only reason people tolerate them is because they are not enforced. But when you do enforce something from them, it's always unjust and unfair, like in this case.
> When someone is routinely dropping lit matches in a dry forest, "he only started one wildfire" is obviously no defense.
He has lots and lots of comments of which only a couple that you didn't like. Absolutely nothing like "routinely dropping lit matches".
Re: Computer Scientists Break Traveling Salesperson Record
#160Earlier quoted context omitted.
Lately it feels like agile is where innovation goes to die :(
I agree. It’s sad. Agile principles are awesome, but by the time you run them through many company’s implementations of Scrum or SAFe or (God forbid) Jira, you may as well just do waterfall. I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.
I have a hunch that one of the reasons "Agile" becomes ruined is the complexity of the stack most teams are using. IIRC, the stories/tasks were originally meant to be able to be completed by anyone on the team with little help from specialists/others within a reasonable time (..including UI?). When the Frontend Engineer needs to wait on Design, coordinate with Backend (ex: discussing API), or even wait for the S3 bucket to be up, mini-waterfalls will be the easiest path to take.