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

Computer Scientists Break Traveling Salesperson Record

quantamagazine.org

Post reply on HN
Print view View original

121–130 of 188 posts

Re: Computer Scientists Break Traveling Salesperson Record

#121

Post by doctor_eval »

robohoe wrote: post #119
pkaye wrote: post #90

Earlier quoted context omitted.

Meanwhile in an agile dev team.... "can you optimize it in the next sprint?"

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.

Re: Computer Scientists Break Traveling Salesperson Record

#122

Post by bigiain »

booleandilemma wrote: post #91
pkaye wrote: post #90

Earlier quoted context omitted.

Meanwhile in an agile dev team.... "can you optimize it in the next sprint?"

“so you don’t have anything to demo, then?”

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

Re: Computer Scientists Break Traveling Salesperson Record

#123

Post by bigiain »

robohoe wrote: post #119
pkaye wrote: post #90

Earlier quoted context omitted.

Meanwhile in an agile dev team.... "can you optimize it in the next sprint?"

Lately it feels like agile is where innovation goes to die :(

Nobody needs too "innovate" another stupid CRUD app though...

I kinda feel all the _actual_ innovation is doing things that align with Agile's underlying principals of valuing individuals/working-software/response-to-changes over processes/documentation/plans - while all th3e people who _talk_ about doing "Agile" rarely follow those principals, and mostly just mean "We have meetings we call 'standups', and negotiated deadlines that we call 'sprints'".

Re: Computer Scientists Break Traveling Salesperson Record

#125

Post by gitgud »

kats wrote: post #29

> 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?

Re: Computer Scientists Break Traveling Salesperson Record

#126

Post by LeoPanthera »

jonbaer wrote: post #105
LeoPanthera wrote: post #52

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?

OR-Tools, https://developers.google.com/optimization/routing/tsp

So I guess if you're not a developer, the answer is "no".

Someone should make a front end for this.

Re: Computer Scientists Break Traveling Salesperson Record

#127

Post by ellis-bell »

sigmaprimus wrote: post #124

I 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?

probably

circuit satisfiability and related hard problems are all reducible to each other

Re: Computer Scientists Break Traveling Salesperson Record

#128

Post by aidenn0 »

bigiain wrote: post #122
booleandilemma wrote: post #91

Earlier quoted context omitted.

“so you don’t have anything to demo, then?”

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 higher speed limits are seen as the lingering effects of the national speed-limit have worn off).

Re: Computer Scientists Break Traveling Salesperson Record

#129

Post by Grustaf »

jfk13 wrote: post #87
Grustaf wrote: post #74

Earlier quoted context omitted.

Sex is not very important for a doctor, for an actor is pretty much defines what roles you can play.

Shakespeare might like a word... (Alternatively: then why don't we have separate words for black actors, white actors, native American actors, south-east Asian actors, transgender actors, and so on?)

I am aware. And there are still contexts when all roles are played by male actors (and perhaps the opposite), but that is not really the point here.

And we are talking about human language here, it's something that has evolved over centuries, to a large extent spontaneously. That's why we make some distinctions and not others that may seem equally important.

If we were talking about a programming language your argument be more relevant, although I would still argue that sex is a much more dramatic difference than race.

Re: Computer Scientists Break Traveling Salesperson Record

#130

Post by Grustaf »

rsynnott wrote: post #111
mattigames wrote: post #109

Earlier quoted context omitted.

So the path forward is to use "male actors" and "female actors" instead of actors and actresses? Doesn't appear to be a net positive for society, is just making them longer to write and pronounce.

Or, just... actors? Like, most of the time when you talk about an actor the gender isn’t that relevant.

When you don't care or know about the gender, you do use the word "actor". Like "I thought all Hollywood actors were divas but you're so down to earth". You wouldn't say "actors and actresses", right?

Sort of like "model". Most of the time you just say "model" and it could be either sex, but if you want to talk specifically about male models you say that.

Post reply on HN