Timeline for Why does this graph show the tightness of MST heuristic's 2-approximation bound?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2020 at 7:08 | vote | accept | oarfish | ||
| Nov 23, 2015 at 15:59 | vote | accept | oarfish | ||
| Nov 17, 2020 at 7:08 | |||||
| Nov 21, 2015 at 12:00 | history | edited | oarfish | CC BY-SA 3.0 | added 10 characters in body |
| Nov 20, 2015 at 18:23 | history | edited | oarfish | CC BY-SA 3.0 | deleted 1 character in body |
| Nov 20, 2015 at 17:15 | history | tweeted | twitter.com/StackCompSci/status/667753054855368704 | ||
| Nov 20, 2015 at 17:08 | history | edited | oarfish | CC BY-SA 3.0 | deleted 23 characters in body |
| Nov 20, 2015 at 11:18 | answer | added | oarfish | timeline score: 4 | |
| Nov 14, 2015 at 16:23 | comment | added | oarfish | @YuvalFilmus See e.g. here courses.engr.illinois.edu/cs598csc/sp2009/lectures/… First, compute an MST. Then double the edges of the MST, obtaining an eulerian tour. Now walk the tour and skip over all nodes already visited by using the edge to the next but one node (or skip as long as the next node is one that has already been visited). | |
| Nov 14, 2015 at 16:16 | comment | added | Yuval Filmus | What is the MST heuristic? | |
| Nov 14, 2015 at 15:18 | comment | added | Raphael | @oarfish The title is the biggest issue; it makes people expect a certain type of question. Then they read things that does not fit at all, they skip the rest and comment. | |
| Nov 14, 2015 at 12:51 | answer | added | Yuval Filmus | timeline score: 4 | |
| Nov 14, 2015 at 8:42 | history | edited | oarfish | CC BY-SA 3.0 | added 68 characters in body |
| Nov 14, 2015 at 8:40 | comment | added | oarfish | I do not see how this type of graph shows that the 2-approximation bound of MST heuristic is tight seems to make my intent clear. How would you suggest to edit the question? | |
| Nov 14, 2015 at 8:39 | comment | added | David Richerby | I suggest you rephrase your question to make that clear. | |
| Nov 14, 2015 at 8:37 | comment | added | oarfish | @DavidRicherby I know why it is no worse than a 2-approximation, this is supposed to be a worst-case instance showing the bound is tight. Or maybe a series of increasing n would have the ratio converge to two. And as far as I understand, the only black edges should be the spokes. Although having nodes in the circle connected with cost 1 does not change the tour I think. | |
| Nov 14, 2015 at 8:35 | comment | added | David Richerby | No single example can "prove that the MST approximation to TSP is a 2-approximation", since being a 2-approximation requires being within a factor of two of optimal on all graphs. What this graph is supposed to do is prove that MST is not better than a 2-approximation, by showing a graph on which it's out by exactly a factor of two. By the way, there should presumably be a black edge from V1 to V6. | |
| Nov 13, 2015 at 23:45 | review | First posts | |||
| Nov 14, 2015 at 8:39 | |||||
| Nov 13, 2015 at 23:44 | history | asked | oarfish | CC BY-SA 3.0 |