from the problem-of-looking-for-an-asymmetric-traveling-salesman dept.
The real-world version of the famous traveling salesman problem finally gets a good-enough solution.
From the abstract on arXiv https://arxiv.org/abs/1708.04215 (full article is available):
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.
[1] LP == Linear Programming
[2] ATSP == Asymmetric Traveling Salesman Problem
Any Soylentils able to explain what, if any, impact this research has on the class of NP-complete problems?
source:
https://www.quantamagazine.org/one-way-salesman-finds-fast-path-home-20171005/
(Score: 5, Informative) by bradley13 on Tuesday October 10 2017, @08:22AM (2 children)
I didn't read TFA, because this is Soylent. However, from TFS:
"We give a constant-factor approximation algorithm..." The word "approximation" means that there is no guarantee of an optimal solution. There are lots of algorithms for getting "pretty good" solutions, or even optimal solutions "most of the time" for NP-complete problems in polynomial time. So: this result presumably offers nothing new, except maybe a different way of doing the approximation.
Everyone is somebody else's weirdo.
(Score: 2) by TheRaven on Tuesday October 10 2017, @10:38AM (1 child)
sudo mod me up
(Score: 0) by Anonymous Coward on Thursday October 12 2017, @07:07PM
> the travelling salesman problem is much easier to solve if you place some constraints
Goodness me yes! It's an absolutely tractable problem under lots of conditions. I forget what boundaries are big-O (complexity) better and which are just empirically useful, but some which have been investigated include: directed graphs, trees, planar graphs, maximum degree (# of edges/node), bounded edge length...
There's some pretty amazing properties where, like including or excluding '0' from the domain of a function, suddenly the problem can have a vastly different meaning.
Any graph maths or CS types around here able to link to an understandable overview of modified travelling salesman?
(Score: 5, Informative) by stormwyrm on Tuesday October 10 2017, @08:43AM
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by turgid on Tuesday October 10 2017, @10:37AM (3 children)
I usually find I get home fastest when I'm on my beer scooter.
I refuse to engage in a battle of wits with an unarmed opponent [wikipedia.org].
(Score: 1, Touché) by Anonymous Coward on Tuesday October 10 2017, @12:02PM (2 children)
But, how many pubs do you stop at on the way home? And do you visit them in an optimal sequence??
(Score: 2) by turgid on Tuesday October 10 2017, @07:06PM
I'm not a One-Way Salesman.
I refuse to engage in a battle of wits with an unarmed opponent [wikipedia.org].
(Score: 2) by bob_super on Tuesday October 10 2017, @09:49PM
Is the "optimal sequence" really based on distance? I thought it was based on high-to-low attractiveness of female patrons, which solves the order-of-visit question and therefore nullifies the TSP altogether.
(Score: 2, Insightful) by All Your Lawn Are Belong To Us on Tuesday October 10 2017, @02:56PM (1 child)
As in, chess programs make sequences of legal moves and then make numeric calculations to evaluate what the board looks like in that condition. Best condition is the played next move. They don't "play" chess the way humans do necessarily (humans think about what the board looks like and try to find optimal next moves but do not assign centipawn values to conditional factors or use hash tabling - at least not that I'm aware of,) but the approximation is now good enough to hold or beat grandmaster level players. But it's only an approximation of the solution.
This sig for rent.
(Score: 0) by Anonymous Coward on Thursday October 12 2017, @07:14PM
> centipawn
Well, sure, but we don't call it that. Though, internally, those silicon neural nets don't 'call' it anything either!
Proof: "it's good to control the middle of the board. But most of the time, not so good that it's worth losing a piece or a pawn over."
Heck, any time two positions look preeeeeetty similarly good, that's a decipawn or centipawn difference. The non-piece-determining conditionals X moves ahead under Y circumstances, admittedly, is not something common to elementary school chess clubs, but certainly the better human chess players consider more than just "can I get a piece through this sequence", and unless the position advantage is "worth" a pawn+, it's definitially pawn-fractional.
Pawn-fractional. Well, thank you soylentil, for expanding my lexicon. Much wordy love!
(Score: 2) by wonkey_monkey on Wednesday October 11 2017, @04:47PM (1 child)
So, not an actual solution then?
systemd is Roko's Basilisk
(Score: 0) by Anonymous Coward on Thursday October 12 2017, @11:16PM
Right. Exactly. This is why it won't transpose to other problems in its class, though the approximation bound *might* morph, for carefully constructed parallel problems.