Video 10-8: Christofides' TSP Algorithm

0:01 In the next section, we'll look at Christophus's algorithm for the traveling salesman problem. It's a very well-known approximation algorithm. It's both uh very simple also ingenious in a way to use the right ingredients and it's for for a very long time it used to be the best we know about this problem in terms of approximation. And so it's it's well worth seeing. Um, if you're learning about approximation algorithms, I think you're supposed to know this one, even though it um might be harder to generalize the techniques used there to other problems. Uh, the problem that we're looking at is the metric traveling salesperson problem. And let me stress that metric is really crucial here. Metric means that the distances between the points obey the triangle inequality. That's all it says. But in general, if you give me an arbitrary TSP instance, who knows what the distances might be like. Uh and in particular, you can show easily that you cannot possibly approximate uh traveling salesperson um with any good constant factor in in the general case because you can always reduce to a Hamiltonian path and there you don't need big weights. So um uh in the general sense traveling salesperson is is uh relatively uh hopeless to get anything in terms of approximation guarantees. Uh if you place this restriction on the distances then we can do something and maybe um the intuition why uh why does the triangle inequality help us in any way?

1:47 uh that might might not be so obvious if you've if you haven't thought about it a bit. Uh let me draw some example and here I'm just going to do an even more restricted special case which is the ukidian traveling salesperson problem where the distances are the ukidian distances of points in the plane. Um now of course yeah it's a complete graph right you always have all distances so uh gets a bit messy to draw um the the big point let me first say the big point about having a triangle inequality means if I somehow have a solution that goes like this it goes via some other city but it turns out as part of my algorithm that It's inconvenient to have this detour in it. I can always instead shortcut it and take the direct edge. And this is never going to make the tour longer. Okay.

3:07 Nobody can read that. reduces the length of the tour and uh you can easily come up with um with distances where that's not the case in the general sense. Uh you need the triangle inequality for that. uh the special case that I'm I'm drawing here just as a side note uh the uklidian tsp is a subset of metric because the uklidian distances uh obey the triangle inequality but it's it's more special and so um in a way um just as as kind of general knowledge even though we're not going to get into this if you know that the distances are uklidian you can do better than uh Christophus's algorithm in particular there's a pas even so you can get arbitrarily good approximations but then the time degrades with epsilon but not so for metric Um at least I think nothing's known. I don't know if this is proven. Uh okay. Um because of this shortcutting you can do a very simple first step which is based on minimum spanning trees. So we start with our our complete graph. It has these weights. All we know is that they obey the triangle inequality which again the key point of triangle inequality is that you can shortcut notes and you're only going to make the tour better. So what we'll do is uh we'll find a spanning tree.

5:01 I'm just going to make up one. Say it looks like this. Maybe like this. Not completely degenerate. Um, we compute this spanning tree. And now you're just going to walk outside around the spanning tree.

5:27 That is a round trip, right? Um, it may visit some vertices several times. It's certainly a Okay, I should maybe give it say we walk around this way. You can always do this in a tree, right? You can always walk around um because this is a planer graph that's a with a single single face. Um and we're using exactly each edge exactly twice.

6:06 But it's not a valid travel and salesperson tour in general because you're visiting this vertex several times. But you can always cut it out and say the tour is not going to be worse. So whenever you say you start arbitrarily here, then you walk around. So you go from here to here. The actual tour would go from this to this. And then it would want to go back here, but you're just going to shortcut. then it would want to go back here, but you're going to shortcut to that vertex instead. Then you again follow the the tour around the tree. Now here you would shortcut. Here you would backtrack, backtrack, backtrack. So you're going to shortcut all the way back. That's the actual tour that you output. That's a valid TSP tour. And the trick is it's not going to be longer than the gray walking all around outside the tree tour, but it's only visiting every vertex uh once.

7:01 And so uh I termed this the babbo baby crystal fetus uh because it's not the full algorithm. Uh but you could do this uh technically you could say I'm taking every edge of the tree making it into two edges two parallel edges. Then the graph is oileran which means it has an oiler cycle. So every edge is used exactly once because now I'm whatever tree I'm starting with if I double every edge it's going to have even degree on every vertex obviously and then it has an oilarian cycle. So you can just follow that oilarian cycle which is if you think about is precisely what we did. It's the same thing. uh it makes it even more obvious that we uh double the weight of the minimum spanning tree by using every edge twice and we use the same shortcutting trick as I just explained whenever you visit a vertex you're trying to visit a vertex another time you skip it and turns out this is a two approximation which is not hard to see we've essentially shown this on the example the tour we initially start with the oiler oileran tour which is not a tsp for we're not a Hamiltonian path cycle uh has cost at most two times the minimum spanning tree cost.

8:24 Okay. And uh shortcutting doesn't make that longer. And also uh if you start from an arbitrary TSP tour say the optimal one and you remove any of the edges then you get a spanning tree which will just be a path. So that also means that the minimum spanning tree which is not restricted to be a path will have cost at most the cost of the optimal tour even minus that edge. So the optimal TSP tour is essentially uh larger than the cost of this of the spanning tree and our tour costs at most two times that. So if you plug that put that together we get a two approximation. Okay. Uh that's already kind of is non non-trivial to come up with this minimum spanning tree idea but not many fancy algorithmic tricks have happened. We can go one step further. uh we can do a little improvement on this and in particular um this oiler tour that we're using on the tree is is a little wasteful in that we're doubling all the edges.

9:41 Uh whereas if you think about some trees say this tree uh it's not a good it's not a good example. Let's let's take the uh the path.

10:02 This is almost oilarian by itself. You can with uh well for an oilerian path it all already works. You can walk back here and then cycle.

10:28 what's another less boring example? Maybe. Oh, come on. >> Someone I want to find out what this bug is that uh causes the cursor to vanish.

10:51 Well, imagine some other tree with even degree apart from the leaves. Um, then you can also try to do an oiler tour that doesn't duplicate all the edges. You may duplicate some, you'll have to duplicate some edges, but not all of them. So the way to do that is uh to take your minimum spanning tree and then take uh all the um uh uh the odd degree vertices and treat them separately. Uh what we'll look at first is a more general lema. So you take an arbitrary subset of your vertices that is even and you take a minimum perfect a minimum cost perfect matching on those vertices. So again, imagine you have some some graph. It's a complete graph. So I'm not going to draw all edges. Uh but you're going to pick it's an even even degree subset. Suppose that's not here. Uh well, let's let's say it's here, but we only look at uh these are the vertices in V prime.

12:08 Some cool some old recording eventually kicked back in. So, uh, say this is not inside of B prime. This is the minimum cost perfect matching. Then any kind of um tour that you're going to make through this graph on this subset uh of of V prime like this that you alternate between edges that are in this perfect matching and that are outside and so you can bound the cost uh more formally. So if you take uh C star to be the the optimum TSP tour and C prime is the tour where you restrict it on the edges the the vertices in your set V prime and you shortcut all others. Uh then you have this this kind of picture. This this edge here is shortcuted. And then it has to be alternating between edges in the matching and edges outside because any kind of detour would be to a vertex that's not part of the that's not matched in the perfect matching. So it can't be perfect. Uh so that's not allowed. So this tour is alternating.

13:36 Well, first of all, yeah, by triangle inequality, we're not making the cost bigger. Um but this restricted tour is the disjoint union of two matching of two perfect matchings of V prime and uh you can get one is the one that you um whether or not you started with one doesn't matter uh you can get two perfect matchings from the optimal TSP tour by taking the odd and even steps and it has to be an is an even even degree. It's an even sized set. So you'll have an even number of edges. So this all has to work out. Uh and then um the cheaper of these two matchings uh we don't know which uh how the costs are distributed but in total their cost is at most that of the TSP tour. And so one of them has to have cost half of the TSP tour.

14:35 All that's left is putting that together into an algorithm for the metric tsp problem and that's Christophus's approximation. Uh the algorithm works as follows. The first part is as we had it before. We compute a minimum spanning tree in the graph. We find the vertices with odd degree in t. Uh there has to be an even number of those by counting edges. And then in the same graph but restricted to this subset of vertices V prime you find a minimum cost perfect matching. Now as a a separate story how to do that uh you can do it in polomial time. I think I mentioned that um and uh in this case the graph is complete. So it's uh it always there's always a perfect matching. The question is just to find the one with minimum cost. Uh but that can be done. uh we're not going to get into the details how uh to do that efficiently. Uh what's left is to put these two things together and um what you do is you just take the tree as is and uh augment it with this matching.

15:41 So uh maybe we can do a tiny cartoon example of what that could look like. So suppose this is our spanning tree. Um maybe it's a bit boring that it has only leaves of odd degrees. So let's add this one. So the odd degree vertices are all the leaves of course. And uh this one, this is even. This is even. And this is going to be paired up by this um minimum perfect matching. Who knows what that looks like? Maybe like this. And you see if you add those then all the uh odd degree vertices in the tree they turned into even degree vertices. So now you can walk around this graph and find an oiler tour. We're using if the algorithms uh for that and that's going to be almost the tour you output. You shortcut repeated vertices just as before.

16:50 So the the tour again would have to follow this until you see a vertex again. So in this case you would just shortcut here and not visit this and this again but that's all. And then the green is the tour you output with the dashed edge. Now how good is this? You can show it's a three half approximation and um all there ingredients are there. The cost of this tour that we output by definition is just using each edge in this graph once. So the total cost of the tour is the cost of the tree edges and the cost of this matching. And uh we've already bounded those in the right way.

17:43 Now this is a relatively simple algorithm. How to come up with this idea of this of taking the tour as the union of a tree in a perfect matching is clever. Um but there's otherwise not not a lot of machinery needed. It's an old algorithm. um one of the earliest uh approximation algorithms that people studied and uh for for 50 years it was almost 50 years I guess it was open whether you can improve this and it turns out you can uh by a tiny bit so there's a a tiny constant it's some non non zero constant positive constant so you can improve the approximation guarantee on metric traveling salesperson problem a little bit with the much more complicated algorithm. Uh just wanted to mention that it it was essentially a PhD project but of a very clever person of course but still uh sometimes uh these really fundamental uh problems find a solution um from an unexpected angle.