Approximation bounds on the Nearest Neighbour Algorithm for the TSP.












-1












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










share|cite|improve this question









$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


















-1












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










share|cite|improve this question









$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
















-1












-1








-1





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










share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










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




















  • $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












1 Answer
1






active

oldest

votes


















0












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






share|cite|improve this answer











$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













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
});


}
});














draft saved

draft discarded


















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









0












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






share|cite|improve this answer











$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


















0












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






share|cite|improve this answer











$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
















0












0








0





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






share|cite|improve this answer











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







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 7 '18 at 4:45

























answered Dec 6 '18 at 17:36









Fabio SomenziFabio Somenzi

6,42321321




6,42321321












  • $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$
    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




















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei