Christofides algorithm (by hand) (suboptimal solution - is it my fault?)











up vote
2
down vote

favorite












I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)





  • $alpha$ denotes the start and end vertex of the Eulerian path
    enter image description here





Step 1 - Calculate minimum spanning tree $T$



enter image description hereenter image description here






Step 2 - Calculate the set of verices $O$ with odd degree in $T$



enter image description hereenter image description here






Step 3 - Form the subgraph of $G$ using only the vertices of $O$



This is starting to get confusing



enter image description here



enter image description hereenter image description here






Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph



enter image description here






Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph



enter image description here





I am NOT satisfied



Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G rightarrow H$ or $A rightarrow B$ as illustrated underneath:



enter image description here










share|cite|improve this question
























  • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
    – Yuval Filmus
    Nov 27 at 21:07










  • @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
    – Sebastian Nielsen
    Nov 27 at 21:46










  • I’m not going to check your solution. I can help you with any conceptual difficulties.
    – Yuval Filmus
    Nov 27 at 21:49















up vote
2
down vote

favorite












I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)





  • $alpha$ denotes the start and end vertex of the Eulerian path
    enter image description here





Step 1 - Calculate minimum spanning tree $T$



enter image description hereenter image description here






Step 2 - Calculate the set of verices $O$ with odd degree in $T$



enter image description hereenter image description here






Step 3 - Form the subgraph of $G$ using only the vertices of $O$



This is starting to get confusing



enter image description here



enter image description hereenter image description here






Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph



enter image description here






Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph



enter image description here





I am NOT satisfied



Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G rightarrow H$ or $A rightarrow B$ as illustrated underneath:



enter image description here










share|cite|improve this question
























  • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
    – Yuval Filmus
    Nov 27 at 21:07










  • @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
    – Sebastian Nielsen
    Nov 27 at 21:46










  • I’m not going to check your solution. I can help you with any conceptual difficulties.
    – Yuval Filmus
    Nov 27 at 21:49













up vote
2
down vote

favorite









up vote
2
down vote

favorite











I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)





  • $alpha$ denotes the start and end vertex of the Eulerian path
    enter image description here





Step 1 - Calculate minimum spanning tree $T$



enter image description hereenter image description here






Step 2 - Calculate the set of verices $O$ with odd degree in $T$



enter image description hereenter image description here






Step 3 - Form the subgraph of $G$ using only the vertices of $O$



This is starting to get confusing



enter image description here



enter image description hereenter image description here






Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph



enter image description here






Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph



enter image description here





I am NOT satisfied



Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G rightarrow H$ or $A rightarrow B$ as illustrated underneath:



enter image description here










share|cite|improve this question















I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)





  • $alpha$ denotes the start and end vertex of the Eulerian path
    enter image description here





Step 1 - Calculate minimum spanning tree $T$



enter image description hereenter image description here






Step 2 - Calculate the set of verices $O$ with odd degree in $T$



enter image description hereenter image description here






Step 3 - Form the subgraph of $G$ using only the vertices of $O$



This is starting to get confusing



enter image description here



enter image description hereenter image description here






Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph



enter image description here






Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph



enter image description here





I am NOT satisfied



Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G rightarrow H$ or $A rightarrow B$ as illustrated underneath:



enter image description here







algorithms graphs graph-theory matching spanning-trees






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 27 at 21:01

























asked Nov 27 at 20:43









Sebastian Nielsen

1185




1185












  • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
    – Yuval Filmus
    Nov 27 at 21:07










  • @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
    – Sebastian Nielsen
    Nov 27 at 21:46










  • I’m not going to check your solution. I can help you with any conceptual difficulties.
    – Yuval Filmus
    Nov 27 at 21:49


















  • Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
    – Yuval Filmus
    Nov 27 at 21:07










  • @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
    – Sebastian Nielsen
    Nov 27 at 21:46










  • I’m not going to check your solution. I can help you with any conceptual difficulties.
    – Yuval Filmus
    Nov 27 at 21:49
















Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
– Yuval Filmus
Nov 27 at 21:07




Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution.
– Yuval Filmus
Nov 27 at 21:07












@YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
– Sebastian Nielsen
Nov 27 at 21:46




@YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right?
– Sebastian Nielsen
Nov 27 at 21:46












I’m not going to check your solution. I can help you with any conceptual difficulties.
– Yuval Filmus
Nov 27 at 21:49




I’m not going to check your solution. I can help you with any conceptual difficulties.
– Yuval Filmus
Nov 27 at 21:49










1 Answer
1






active

oldest

votes

















up vote
5
down vote



accepted










As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of



On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$alpha$ should be replaced by edge HG.






share|cite|improve this answer























  • Yes, thank you a lot! This is the error I had trouble finding!
    – Sebastian Nielsen
    Nov 28 at 8:40











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


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f100618%2fchristofides-algorithm-by-hand-suboptimal-solution-is-it-my-fault%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








up vote
5
down vote



accepted










As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of



On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$alpha$ should be replaced by edge HG.






share|cite|improve this answer























  • Yes, thank you a lot! This is the error I had trouble finding!
    – Sebastian Nielsen
    Nov 28 at 8:40















up vote
5
down vote



accepted










As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of



On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$alpha$ should be replaced by edge HG.






share|cite|improve this answer























  • Yes, thank you a lot! This is the error I had trouble finding!
    – Sebastian Nielsen
    Nov 28 at 8:40













up vote
5
down vote



accepted







up vote
5
down vote



accepted






As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of



On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$alpha$ should be replaced by edge HG.






share|cite|improve this answer














As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of



On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$alpha$ should be replaced by edge HG.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 27 at 23:59

























answered Nov 27 at 22:25









Apass.Jack

4,8041329




4,8041329












  • Yes, thank you a lot! This is the error I had trouble finding!
    – Sebastian Nielsen
    Nov 28 at 8:40


















  • Yes, thank you a lot! This is the error I had trouble finding!
    – Sebastian Nielsen
    Nov 28 at 8:40
















Yes, thank you a lot! This is the error I had trouble finding!
– Sebastian Nielsen
Nov 28 at 8:40




Yes, thank you a lot! This is the error I had trouble finding!
– Sebastian Nielsen
Nov 28 at 8:40


















draft saved

draft discarded




















































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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


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


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%2fcs.stackexchange.com%2fquestions%2f100618%2fchristofides-algorithm-by-hand-suboptimal-solution-is-it-my-fault%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

AnyDesk - Fatal Program Failure

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

QoS: MAC-Priority for clients behind a repeater