Is there an efficient solution to the travelling salesman problem with binary edge weights?
3
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited yesterday
Apass.Jack
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
3
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited yesterday
Apass.Jack
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
3
3
3
2
$begingroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
edited yesterday
Apass.Jack
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?
traveling-salesman
traveling-salesman
edited yesterday
Apass.Jack
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Apass.Jack
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Apass.Jack
13.5k1940
edited yesterday
Apass.Jack
13.5k1940
edited yesterday
Apass.Jack
13.5k1940
13.5k1940
asked yesterday
WiccanKarnakWiccanKarnak
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
WiccanKarnakWiccanKarnak
1185
asked yesterday
WiccanKarnakWiccanKarnak
1185
1185
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
WiccanKarnak is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
7
$begingroup$
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)
answered yesterday
j_random_hackerj_random_hacker
2,91211016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
|
show 1 more comment
2
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
WiccanKarnak is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
7
$begingroup$
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)
answered yesterday
j_random_hackerj_random_hacker
2,91211016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
|
show 1 more comment
7
$begingroup$
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)
answered yesterday
j_random_hackerj_random_hacker
2,91211016
$endgroup$
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
|
show 1 more comment
7
7
7
$begingroup$
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)
answered yesterday
j_random_hackerj_random_hacker
2,91211016
$endgroup$
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)
answered yesterday
j_random_hackerj_random_hacker
2,91211016
answered yesterday
j_random_hackerj_random_hacker
2,91211016
answered yesterday
j_random_hackerj_random_hacker
2,91211016
answered yesterday
j_random_hackerj_random_hacker
2,91211016
2,91211016
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
|
show 1 more comment
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
3
3
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
I initially read the question with the assumption it's asking about complete graphs - but then you can still get the Hamiltonian Cycle problem by asking if a zero-length Hamiltonian cycle exists. And if you allow retrace, the problem becomes trivial.
$endgroup$
– John Dvorak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
@JohnDvorak thanks a lot, is there a way if I guarantee no Hamiltonian Cycles?
$endgroup$
– WiccanKarnak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
Every complete graph has a Hamiltonian cycle. And if your graph doesn't have a Hamiltonian cycle ... then it definitely doesn't have a Hamiltonian cycle, so what was the question again?
$endgroup$
– John Dvorak
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
@WiccanKarnak : (A TSP solution is a Hamiltonian cycle ... of minimal total weight.)
$endgroup$
– Eric Towers
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
$begingroup$
Aren't you allowed to use the same edge twice in TSP?
$endgroup$
– immibis
yesterday
|
show 1 more comment
2
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
add a comment |
2
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
$endgroup$
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
add a comment |
2
2
2
$begingroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
$endgroup$
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.
However, it is simple to reduce HAMILTON-CYCLE to $0$–$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$–$1$ TSP is NP-complete.
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
answered yesterday
David RicherbyDavid Richerby
69.1k15106195
69.1k15106195
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
add a comment |
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
This is a good point, though the choice of whether to require the input graph to be complete or not never makes a practical difference (for the purpose of finding a distance-minimal tour, missing edges in a graph can be encoded as arbitrarily-distant edges in a complete graph). Interestingly, in looking for a definitively canonical definition of the TSP problem, I found that on p. 211 of Garey & Johnson (1979) they require the edge weights to be in $mathbb Z^+$ -- i.e., 0-length edges are forbidden, meaning that for them, the "0-1 TSP" described here is technically not a special case of TSP!
$endgroup$
– j_random_hacker
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
$begingroup$
@j_random_hacker It's a good job I'm only throwing small stones in my glass house! (Actually, you can reduce $0$-$1$ TSP to $1$-$2$ TSP by just adding one to every edge weight and adding $n$ to the length of the path you're looking for.)
$endgroup$
– David Richerby
16 hours ago
add a comment |
WiccanKarnak is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
WiccanKarnak is a new contributor. Be nice, and check out our Code of Conduct.
WiccanKarnak is a new contributor. Be nice, and check out our Code of Conduct.
WiccanKarnak is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105984%2fis-there-an-efficient-solution-to-the-travelling-salesman-problem-with-binary-ed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
