Approximation bounds on the Nearest Neighbour Algorithm for the TSP.
$begingroup$
I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP.
I came across this paper :
Rosenkrantz, Daniel & Edwin Stearns, Richard & M. Lewis II, Philip. (1977).
An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM
J. Comput.. 6. 563-581. 10.1137/0206041.
I however am I bit confused because, in page 564 it says that this can also apply to the classical tsp problem. However, in the paragraph after it, it says that it does not. Can anyone help clarify this?
computer-science
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
$endgroup$
add a comment |
$begingroup$
I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP.
I came across this paper :
Rosenkrantz, Daniel & Edwin Stearns, Richard & M. Lewis II, Philip. (1977).
An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM
J. Comput.. 6. 563-581. 10.1137/0206041.
I however am I bit confused because, in page 564 it says that this can also apply to the classical tsp problem. However, in the paragraph after it, it says that it does not. Can anyone help clarify this?
computer-science
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
$endgroup$
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14
add a comment |
$begingroup$
I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP.
I came across this paper :
Rosenkrantz, Daniel & Edwin Stearns, Richard & M. Lewis II, Philip. (1977).
An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM
J. Comput.. 6. 563-581. 10.1137/0206041.
I however am I bit confused because, in page 564 it says that this can also apply to the classical tsp problem. However, in the paragraph after it, it says that it does not. Can anyone help clarify this?
computer-science
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
$endgroup$
I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP.
I came across this paper :
Rosenkrantz, Daniel & Edwin Stearns, Richard & M. Lewis II, Philip. (1977).
An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM
J. Comput.. 6. 563-581. 10.1137/0206041.
I however am I bit confused because, in page 564 it says that this can also apply to the classical tsp problem. However, in the paragraph after it, it says that it does not. Can anyone help clarify this?
computer-science
computer-science
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
asked Dec 6 '18 at 14:47
Dylan GaleaDylan Galea
103
103
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14
add a comment |
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
$endgroup$
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f3028584%2fapproximation-bounds-on-the-nearest-neighbour-algorithm-for-the-tsp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
$endgroup$
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
add a comment |
$begingroup$
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
$endgroup$
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
add a comment |
$begingroup$
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
$endgroup$
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
edited Dec 7 '18 at 4:45
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
answered Dec 6 '18 at 17:36
Fabio SomenziFabio Somenzi
6,42321221
6,42321221
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
add a comment |
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
@Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP?
$endgroup$
– Dylan Galea
Dec 7 '18 at 3:11
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $alpha(n)$, TSP cannot be approximated within a factor of $alpha(n)$, unless P = NP."
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 4:39
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
@Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known
$endgroup$
– Dylan Galea
Dec 7 '18 at 7:53
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
$begingroup$
Yes, if we knew that P $neq$ NP, we would know that there is no way to approximate TSP within a factor of $alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly.
$endgroup$
– Fabio Somenzi
Dec 7 '18 at 7:59
add a comment |
Thanks for contributing an answer to Mathematics 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.
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%2fmath.stackexchange.com%2fquestions%2f3028584%2fapproximation-bounds-on-the-nearest-neighbour-algorithm-for-the-tsp%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
$begingroup$
I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please?
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:04
$begingroup$
@DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it.
$endgroup$
– Dylan Galea
Dec 6 '18 at 15:12
$begingroup$
well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P
$endgroup$
– DanielOnMSE
Dec 6 '18 at 15:14