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?”
"This sounds like a ten-pointer."
Computer Scientists Break Traveling Salesperson Record
141–150 of 188 posts
Re: Computer Scientists Break Traveling Salesperson Record
#142> 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.
So 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.
Wonder 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.
Re: Computer Scientists Break Traveling Salesperson Record
#143Earlier 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.
Two weeks ago I heard a colleague say: "I'm a scrum master in a waterfall project". That was my last week at that IT consulting company and really confirmed my choice to switch to a career with more purpose.
Re: Computer Scientists Break Traveling Salesperson Record
#144Or use deep learning to generate solutions 2 orders of magnitude faster with some minor accuracy loss. https://arxiv.org/pdf/1905.05567.pdf
Pretty much any decent off the shelf algorithm is faster than deep learning if you allow it the same accuracy loss.
Re: Computer Scientists Break Traveling Salesperson Record
#145Earlier quoted context omitted.
There 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/
I believe that this is about a different type of TSP problem, where the distances between cities are defined by the geometric distance from their coordinates in some plane (or on a sphere). This is a simpler problem than when the distances are specified as (whole) numbers.
Geometric distance implies symmetry, asymmetric TSP can be converted to symmetric by doubling the number of vertices.
Re: Computer Scientists Break Traveling Salesperson Record
#146Earlier quoted context omitted.
I disagree, it's extremely common to ask "what was the actress in that movie we just saw?" (so it's clear they are not asking about the male protagonist) or for awards "who you think is gonna be the best actress this year?" or for castings "what actress your think should be casted for the new remake of Romeo and Juliet?"
“Who was that actress in Sex and the City?” This level of specificity probably only works for media in which there’s only one main female character.
Just because it isn’t always enough doesn’t mean it’s useless. Cutting the search space in half by choosing a different word is pretty convenient.
Re: Computer Scientists Break Traveling Salesperson Record
#147Earlier quoted context omitted.
> 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%…
> 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#Co...
Right, 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.
Re: Computer Scientists Break Traveling Salesperson Record
#148> 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.
So 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.
This is very interesting.
Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
Re: Computer Scientists Break Traveling Salesperson Record
#149Earlier quoted context omitted.
Sex is not very important for a doctor, for an actor is pretty much defines what roles you can play.
So does height, in that if you’re 5’6 you won’t manage a very convincing Lincoln. But it’s not generally worked into the job name.
What was Othollo's height? Or Hamlet's? Does anyone care? Height isn't very important for 99% of roles.
Re: Computer Scientists Break Traveling Salesperson Record
#150Earlier quoted context omitted.
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.
Two weeks ago I heard a colleague say: "I'm a scrum master in a waterfall project". That was my last week at that IT consulting company and really confirmed my choice to switch to a career with more purpose.
Is that a euphemism for unemployed?