How to show that the Nearest Neighbour Algorithm given an instance of the metric travelling salesman problem...
$begingroup$
I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of Rosenkrantz et al. : https://disco.ethz.ch/courses/fs16/podc/readingAssignment/1.pdf
What I have difficulty in is Lemma 1 in this paper in the part where the lower bound $sum_{i in H} alpha_i l_i$ $geq$ 2 $sum_{i = k+1}^{min(2k, n)} alpha_i l_i$ is given. Can anyone help in clarifying where this lower bound has come from? Why is it assumed in the paper that the first $k$, $l_i$'s have $alpha_i$ = 0?
algorithms computer-science
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
$endgroup$
add a comment |
$begingroup$
I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of Rosenkrantz et al. : https://disco.ethz.ch/courses/fs16/podc/readingAssignment/1.pdf
What I have difficulty in is Lemma 1 in this paper in the part where the lower bound $sum_{i in H} alpha_i l_i$ $geq$ 2 $sum_{i = k+1}^{min(2k, n)} alpha_i l_i$ is given. Can anyone help in clarifying where this lower bound has come from? Why is it assumed in the paper that the first $k$, $l_i$'s have $alpha_i$ = 0?
algorithms computer-science
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
$endgroup$
add a comment |
$begingroup$
I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of Rosenkrantz et al. : https://disco.ethz.ch/courses/fs16/podc/readingAssignment/1.pdf
What I have difficulty in is Lemma 1 in this paper in the part where the lower bound $sum_{i in H} alpha_i l_i$ $geq$ 2 $sum_{i = k+1}^{min(2k, n)} alpha_i l_i$ is given. Can anyone help in clarifying where this lower bound has come from? Why is it assumed in the paper that the first $k$, $l_i$'s have $alpha_i$ = 0?
algorithms computer-science
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
$endgroup$
I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of Rosenkrantz et al. : https://disco.ethz.ch/courses/fs16/podc/readingAssignment/1.pdf
What I have difficulty in is Lemma 1 in this paper in the part where the lower bound $sum_{i in H} alpha_i l_i$ $geq$ 2 $sum_{i = k+1}^{min(2k, n)} alpha_i l_i$ is given. Can anyone help in clarifying where this lower bound has come from? Why is it assumed in the paper that the first $k$, $l_i$'s have $alpha_i$ = 0?
algorithms computer-science
algorithms computer-science
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
edited Dec 10 '18 at 16:07
Dylan Galea
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
asked Dec 10 '18 at 16:00
Dylan GaleaDylan Galea
103
103
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $alpha_i$ suitable.
$$sum alpha_i l_i = a_0 l_0 + ldots + a_kl_k + ldots + a_{min(2k,n)} l_{min(2k,n)}
= 0 l_0 + ldots + 0l_k + ldots + 2 l_{k+1} + ldots + 2 l_{min(2k,n)}$$
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
$endgroup$
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
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%2f3034099%2fhow-to-show-that-the-nearest-neighbour-algorithm-given-an-instance-of-the-metric%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$
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $alpha_i$ suitable.
$$sum alpha_i l_i = a_0 l_0 + ldots + a_kl_k + ldots + a_{min(2k,n)} l_{min(2k,n)}
= 0 l_0 + ldots + 0l_k + ldots + 2 l_{k+1} + ldots + 2 l_{min(2k,n)}$$
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
$endgroup$
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
add a comment |
$begingroup$
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $alpha_i$ suitable.
$$sum alpha_i l_i = a_0 l_0 + ldots + a_kl_k + ldots + a_{min(2k,n)} l_{min(2k,n)}
= 0 l_0 + ldots + 0l_k + ldots + 2 l_{k+1} + ldots + 2 l_{min(2k,n)}$$
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
$endgroup$
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
add a comment |
$begingroup$
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $alpha_i$ suitable.
$$sum alpha_i l_i = a_0 l_0 + ldots + a_kl_k + ldots + a_{min(2k,n)} l_{min(2k,n)}
= 0 l_0 + ldots + 0l_k + ldots + 2 l_{k+1} + ldots + 2 l_{min(2k,n)}$$
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
$endgroup$
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $alpha_i$ suitable.
$$sum alpha_i l_i = a_0 l_0 + ldots + a_kl_k + ldots + a_{min(2k,n)} l_{min(2k,n)}
= 0 l_0 + ldots + 0l_k + ldots + 2 l_{k+1} + ldots + 2 l_{min(2k,n)}$$
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
answered Dec 12 '18 at 23:31
Loreno HeerLoreno Heer
3,35411534
3,35411534
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
add a comment |
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
but why are we assuming that $alpha_i = 2 $ $forall$ $i geq k+1$?
$endgroup$
– Dylan Galea
Dec 13 '18 at 12:56
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
The $alpha_i$ have to sum to the number of edges in $T$ and can be at most 2. Therefore if we set all $alpha_0, ldots, alpha_k = 0$ we must set the rest of them to 2 so they add up to $2cdot (min(2k, n) - k -1)$
$endgroup$
– Loreno Heer
Dec 13 '18 at 13:08
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
Though I think it must be shown that the lower bound holds for any configuration of the alphas. Though, since this holds other cases are trivial.
$endgroup$
– Dylan Galea
Dec 13 '18 at 13:12
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
$begingroup$
I think another important issue not mentioned in the paper is that the $l_i$'s must be positive.
$endgroup$
– Dylan Galea
Dec 13 '18 at 18:00
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%2f3034099%2fhow-to-show-that-the-nearest-neighbour-algorithm-given-an-instance-of-the-metric%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
