# R9. Approximation Algorithms: Traveling Salesman Problem

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=zM5MW5NKZJg
**Transcript page:** https://www.withtranscript.ai/video/zM5MW5NKZJg

## Chapters

- 0:00 — Chapter 1 (0:00)
- 2:47 — Chapter 2 (2:47)
- 5:10 — Chapter 3 (5:10)
- 10:28 — Chapter 4 (10:28)
- 15:10 — Chapter 5 (15:10)
- 19:58 — Chapter 6 (19:58)
- 22:12 — Chapter 7 (22:12)
- 26:46 — Chapter 8 (26:46)
- 30:09 — Chapter 9 (30:09)
- 31:58 — Chapter 10 (31:58)

## Transcript

**[0:00]:** The following content is provided under a Creative Common License. Your support will help MIT Open Courseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT Open Courseware at ocw.mmit.edu.

**[0:21]:** So today we're going to look at approximation algorithms for the traveling salesman problem. So you should so I hope everyone knows what the trouble and salesman problem is. You have a graph you're trying to visit every vertex and you want to do this. So you start at a vertex you visit every single one and you end at the starting vertex and you want to do that in the shortest possible time or distance or whatever the metric is. So unfortunately this is np hard also the approximation algorithms for any constant approximation is also known to be np hard. Um so you should have gone over approximation algorithms in lecture. So basically uh let's say the optimal solution has some value v and if you want to calc if you want to guarantee that your algorithm will end up with a value which is within a constant factor of v

**[1:04]:** so less than cv that that is an approximation algorithm but for the traveling salesman problem the approx constant approximation algorithms are also np hard so instead we we modify it slightly so on the traveling salesman problem we impose something called a metric so the important relation here is this one so first of all Let's go through this. So you have a distance metric for so if X Y are vertices your distance is always greater than zero which is reasonable. Your this undirected which is this relation and you have the triangle inequality which means that if you have three vert vertices and you have distances like this distance is always smaller than the sum of these two distances which is at least like real worldish things that make sense right if if this system was longer you would just take this path instead. So the distance by taking another node is always greater than equal to the direct distance.

**[1:58]:** So turns out the metric ts problem is also np hard. So not nothing very great there. But but you can do a constant approximation here and we'll go through two approximations today. The first the simpler one is a two approximation

**[2:17]:** and then we'll improve this to 3 over2. So let's start with the first one. So before we begin, let's uh define a couple of terms. Let's define C of S. So let's so what is S? So let S be a path or rather let's say S is a set of edges.

**[2:47]:** So if you have your graph here,

**[2:52]:** your set of edges could be something like this, this, this, this. So that that's set of edges. And C of S is defined as the sum of the sum of the weights of all the edges. And this actually should be a multi set because you can have you can count the same edge twice. So you can count this edge three times or whatever you want, how many however many times you want. So that's the definition. So now we want to find a cycle which goes through all the vertices and we want to minimize the cost of that cycle. So let's say your optimal so this is this should remind you of the Hamiltonian cycle problem. So this is essentially finding a Hamiltonian cycle in the graph of minimum weight. So this is worse than the Hamiltonian cycle problem. This is finding the minimum weight Hamiltonian cycle.

**[3:36]:** Okay. So let's say there exists this beautiful Hamiltonian cycle which is min you know of is of minimum weight. Let's call that h star g. So it's the best Hamiltonian cycle on this graph and that's the shortest path that your traveling salesman can take. And so the cost of that is given by cf sg. Okay. So how do we go about trying to approximate this problem? So think about what algorithms you've seen that can that sort of connect all the vertices of a graph and minimize costs of edges. Remind you of anything polomial that you've seen in the class that connects all the vertices

**[4:21]:** spans all the vertices. Exactly. So Chris call min spanning tree. So min spanning tree is polomial time and it connects all the vertex vert. So let's let's take some graph. Let's just go with this one. So you have some vertices and you connect you make a minimum spanning tree out of them. Now clearly this is not a cycle yet. But let's try to construct a path out of this minimum spanning tree. So first let's root it. So let's say we have rooted minimum spanning tree. Let's say this is the root. So you have three things coming out of there. I think that's it. Okay. So let's give these labels.

**[5:10]:** So now what we're going to do is the way we're going to traverse all the vertices. Let's just do a DFS. So in DFS traversal you'll first C1 then you'll go down in C2 then go down in C3 then you'll go back up C2 again then go back down C4 go back up C2 one 5 1 6 so basically you're ignoring the rest of the graph you find your minimum spanning tree and you follow all the paths follow them back up and just do a DFS reversal and that is and then you go reach back to one I think And then you have this well it visits all the vertices. It visits some of them more than once which is a problem which we'll deal with shortly. But it visits all the vertices and it's a cycle. So now the problem is the travel and salesman problem does not allow you to visit vertices more than once because if you did not have this restriction you could shorten your path length by going to a separate vertex

**[6:06]:** and coming back or something like that. So let's make that more concrete. So at least so in this case given this triangle inequality I claim that you can just delete the duplicate vertices. So let's look at the duplicate ones. You have 1 2 3 this repeats. So you delete that repeats repeats repeats and that's cycling back. So how do you delete things? So in this case you had a path right? You were going to one to two and two to three to two and so on. So let's draw the four in. So this is following only the tree edges. So how would you delete this? So let's say you find the first duplicate vertex and you don't want that. That's not allowed. So all you do is simply you follow the path and you bypass it. And by the triangle inequality, you know that bypassing it will will never increase your cost.

**[6:55]:** It'll decrease it or like keep it the same. So you can remove the duplicate vertex in this path just bypassing it with also remember that this is a complete graph. So a metric is defined on all pairs of vertices. So every edge exists with some value. So that also follows by the triangle inequality. So if an edge does not exist, just make it the sum of the So if XZ is not an edge, just make it the sum of XY plus YZ. So in any case, so so you construct the an initial path just by going down the tree and doing a naive DFS reversal and then you correct that path by skipping over the duplicates. So finally you'll end up with after skipping over the duplicates you get a 1 2 3 4 5 6 1 and that's a valid cycle right. So so let's call this minimum spanning tree t.

**[7:44]:** So that's your mst and you are removing duplicate edges and getting a cycle c let's say. So now you know that um actually let's take another step back. Let's say okay let's say let's define let's define a cycle first which is so let's say let's call this cycle this guy is C and then you're going from C and you're deleting the duplicates and you're getting C dash so now what you have is cost of C dash it's a valation but anyway Okay, the cost of C dash is less than equal to cost of C. And what is the cost of C? If you know the weight of your minimum spanning tree, what is the cost of C? C is just doing a GFS reversal. So what is the cost of C? If you have if you know your minimum spanning tree,

**[8:51]:** no. So you're traversing every edge on the minimum spanning tree twice. So you're doing a DFS travers, right? So you're going down, you're coming back up. It's like you're going down, coming back up, backtracking, going back down. So every edge is reversed twice. So it's exactly twice D. So let's bring up a different board. So you know that cost of C is twice the cost of T. Does that make sense? Why the traversal implies that you have every edge being visited twice, right? Okay. So now our claim is that the C dash cycle is uh two approximation of the actual Hamilton actual cycle. So why is that? So we already proved. So this impli also implies that C of C dash is less than equal to 2 of CT. Realize that this is not a valid cycle but this is a valid cycle. Okay. So now we need to show that this is somehow bounded by H star G.

**[9:51]:** So how do you do that? Well, look at HRG. What is HRG? HRG is just a cycle which goes the optimal cycle which goes through all the vertices and comes back to the parent vertex. So what you can do? So this is a star of G. This is the optimal thing. Now you can take an edge E here and delete it and then you will get a spanning tree because this is your optimal cycle. Remove one edge and you get a spanning tree. So let's call that t ddash.

**[10:28]:** Does that make sense why that is a spanning tree? Because you had a cycle and you move one edge. So it's touches all the vertices and has and it's a tree. So it's a spanning tree but it's not the minimum spanning tree. So you know that H star G the cost of H star of G is greater than equal to the cost of H star of G minus the edge we removed is greater than equal to the cost of T. Make sense? So you removed one edge and then that that is still greater than the minimum spanning tree. So now combining this guy and this guy you get cost of C dash is less than equal to 2 * cost of C. But you know cost of C is less than cost of H of G. So you get a two approximation.

**[11:32]:** So does that make sense?

**[11:36]:** Okay. Okay. So that was a true approximation. That was pretty straightforward. You just constructed a spanning tree. You did a DFS reversal, remove duplicates, and you have a nice path. But okay, let's just leave it down. But here's the thing. It seems kind of wasteful to go through all the edges when you don't need to. So you're traveling down the tree, you're going back up, and you're you're traversing every edge twice. So it seems kind of ridiculous that you would be doing every edge twice. Doesn't So what could you do better? Well, before we introduce that, let's prove a couple of lemmas, let's so first we we start with this. So let's say S is a subset of V. So you have a graph and you take make a subgraph. So you so you pick out some vertices. So pick out this one and this one and this one and this one and that is your S.

**[12:33]:** And so you get a new graph which contains just those vertices and whatever edges connect them. So the claim is that that that graph also has a Hamiltonian cycle the minimum cost Hamiltonian cycle which is also the traveling salesman solution. So let's call that h star of s. So is some cycle which looks like this I guess here. So h star of s. Now the claim is that the cost of h star of s is less than equal to cost of h star of g. That should make intuitive sense because you're taking only some of the vertices and trying to traverse them. And in this case you're trying to traverse all the vertices. However, this is not this is not this is only true because of the triangle inequality. And let's see why that is the case. So let's say let's so proof by contradiction.

**[13:29]:** Say cost of har of s is actually greater than cost of h star of g. Okay. So look at h star of g. It's a cycle, right? So you have something that your cycle and in this cycle you have all the vertices of s. So pick them out.

**[13:59]:** And now so you have a cycle which has cost less than the optimal cycle in S but it contains all the vertices in S. So what you can do is now you can use the skipping lema from before. So instead of so last time you remove duplicate vertices but this time what you'll do is instead you'll just skip over this vertex and you'll skip over this vertex and so every vertex that's not an S skip over it and that can only decrease the cost. So now you've constructed another cycle which contains only the vertices of S. So it's a Hamiltonian cycle for S but it has cost less than equals H star G which means that this this can never be true. So that is the reason so so the important fact is there that if you have a subset of vertices making the the restricted graph the Hamiltonian cycle is always less than equal to the cost of the Hamilton minimum

**[14:48]:** Hamiltonian cycle is always less than equal to the one in the original graph. So intuitively that should make sense. That's the proof. Okay, next thing is something which might seem unrelated right now. Uh perfect matchings.

**[15:10]:** So, so we've seen perfect matchings in the context of bipartite graphs, right? So, you find the minimum cost perfect matching. You do this flow thing. You send all the flow in and then you connect the vertices with the capacities and whatever. So turns out in a complete graph uh you can still do perfect matching. So perfect matching is you have a bunch of so let's say you need to have an even number of vertices right have perfect matching. So let's say you have these vertices and so this is the perfect matching. So every vertex has one edge coming out of it uh exactly one edge coming out of it and it needs to be even because otherwise it doesn't work out. So that's perfect matching and the minimum cost perfect matching is the minimum among among all all such things and you did this for bipartite graphs.

**[15:50]:** It's fine with flow networks. You can so I'm not going to go into the algorithm for this. It's kind of complicated but it uses linear programming and you can find this for complete graph and it's polinomial. That's good. So given a complete graph you can find the perfect matching is what you should assume for now. Okay. One last thing we want to introduce is so that's called it's oiler circuits. So who who has heard of oiler circuits before? Okay. So,

**[16:34]:** so the reason we're So, okay, let's go back to the what we did before. We had a tree and we were the best way found to traverse it was just going down and going back up and going down and sort of messy. So, what we would rather want to do is sort of traverse the thing without repeating edges. So I don't know if you've probably seen this puzzle before. So you you have you have this graph given to you and the task is to draw this graph without lifting your pen off the paper. So for for example in this graph you could start here go here go here and come back and something and there you go. So you can do that then if you but if you add on like another thing another lobe here then you can't make a circuit. You can still make a path I believe if you add another one you can't even make a path.

**[17:25]:** So how does this work? Let's see. So um let's say forget about the graph for now. Let's say you're just drawing. So you start somewhere. You go to a vertex. Go to another vertex. Come back. Go to this vertex. Leave it. come back. And so observe that whenever you're making this drawing, you go to a vertex and you leave it. Every time you hit a vertex, you leave it. Since this is a circuit, you just loop around and every time you enter a vertex, you have to leave it. What that means is that even though this is not directed, if you like drew out the actual path, you would see the number of vertices go number of edges going into a vertex is equal number of ones leaving. Which means that every degree has to be even. So if you go and look at this graph which is with added loes, this degree is not even.

**[18:16]:** Neither is this, neither is this, neither is this. They're all five, I think. Yeah, they're all five. Which means that this this can never have oiler circuit. So a graph can only have an oiler circuit if it has even degrees for every vertex. And the other way is also true. If a graph has even degrees on every vertex, then it must have an oiler circuit. That's not harder to prove, but like there's a constructive algorithm you can use. So let's say you're given this graph for instance. You would just you would simply go through the graph just like start at some random node and then like go through can keep following edges till you can no longer follow edges. So let's say you stop here then you pick another edge and start and so on and then you can like splice these cycles together at some point.

**[18:57]:** So it's kind of a hand wavy argument but it should be sort of intuitive why you can construct another path given an even degree. You just perform searches. You just create cycles and you splice them together. But for now, I just take it as fact that give a graph as an oiler circuit as in you can draw it without lifting your pen off if and only if every vertex has even degree. So why is that interesting? So let's say we could add some edges to our tree and turn it into turn it into one of those nice graphs. Right? Now this is not right. This is vertic degree 1 degree 1 degree 3 degree 1 degree 1 degree three. All of them are odd but that's not good. But let's say you could add some edges in, turn it to an oiler circuit and then you could do a nice reversal of it and maybe that'll give you a better approximation.

**[19:43]:** So with that hope, let's look at the algorithm. So what you do is you go back to your tree.

**[19:58]:** Let's just leave it at that. So now let's see. So this is degree two. That's good. This is degree three. That's not good. Degree one. This is fine. This is degree one. This also has degree one. This is degree three. Actually, let's let's get rid of this. It does not have degree three. That's a lot of vertices. Okay, there we go. So in this graph, you see that you have 1 2 3 4 five vertices which have degree odd. So now we would like to add some edges to make to turn this set of turn this into another circuitable graph. So how do we do that? So let's call the set of odd edges S.

**[20:47]:** It's odd vertices. Sorry.

**[20:55]:** So you take the set of odd degree vertices. Now go back to perfect matchings. So what does a perfect matching do? It adds edges to that graph so that everything gets degree increased by one. So if you increase the degree of all the odd vertices by one, everything turns even. Right? So you take the set of odd vertices. Okay. Another thing to observe, realize that how many odd verses can you have? Can you have an odd number of odd vertices? Because that would that would that would screw up the whole thing where we needed an even number of things. So, so why why could can you why why is that not possible? Why can you not have an odd number of odd vertices? So, the thing is that let's say let's say you have some graph and what is the sum of the degrees of the graph?

**[21:51]:** Let's move to a different board for this. So you have a graph G and you want the sum of degrees. So DI is the degree for all V. So what is this equal to? So let's say you have this graph.

**[22:12]:** So now if you count the degrees of every vertex, you're basically counting the number of edges coming out, which means that every edge is counted twice. Once for its this end point, once for this end point. This edge is counted twice for here and here. This edge is also counted twice. So basically the sum of the degrees is nothing but 2 * mod of e. Does that make sense? Right? So this is even. Now let's say you take only the odd vertices out. So you the even vertices are good. This is good. This is good. This is not good. This is also not good. This is Yeah. So these are the odd vertices. So the sum of the degrees of the even vertices are by definition even even. So if you remove them the sum of the odd vertices should also remain even. And so you have the sum of odd degrees becoming even which means that you need to have an even number of them.

**[23:10]:** Make sense? So going back to this, so there's a lot of lot of branching off here, but going back to the main point here is that you have an even number of odd vertices. So consider the restriction of the original graph G to this set S. So now we're going to the first thing we did there where we considered a restriction of the graph to a certain set of vertices. So you take the set. So 1 2 3 4 5. So you take these five vertices

**[23:42]:** and you consider the graph that is restricted to these five vertices. Oh sorry there should be six. Oh there's there we go. That's the other one.

**[23:56]:** So those are your six vertices which have odd degrees. Now you find a perfect matching with your polinomal sign algorithm and you get something. So you can now add those edges back in here. So these are your new edges and let's say and something this one. Okay. So you get three new edges and now realize that all the degrees are now even. So now you can do your circuit also. So let's call this matching M. So this is a set of edges M. Let's call the original tree T and the new thing that is formed is T union M. So you're taking all the edges from T and you're adding all the edges from M. So realize that you can have multiple edges, but that's fine because oiler circuits allow you to have multiple edges. So now you take this graph and you find this oiler circuit.

**[24:51]:** So that is basically this thing. So the set of edges in some order and that order exists. So the cost of the oiler circuit let's call it C is equal to the cost of T plus the cost of M right because you're traversing all the edges in your graph. So that is the cost circuit. Now my claim is that so this this is visiting all the nodes in the graph and remember you can do the whole dup duplication argument from before where so where was that ah there so you can do the duplication argument so you're visiting all the edges in the graph all the vertices in the graph you remove the duplicates and you have a valid path now let's see if this valid path is actually uh a better approximation So, so again you will go from C. So this C will go to C dash

**[25:49]:** and this will give you as before uh cost of C dash is less than equal to cost of C. So now you're only interested in cost of C. So what are we doing there? So we know that the cost of C is equal to cost of T plus the cost of M. So from the previous problem we know that the cost of t is less than equal to the cost of h star of g right. So this is less than equal to cost of h star g. So this guy is less than the optimal hamiltonian path. What about this guy? Well, so let's take let's look at the actual H star G again.

**[26:46]:** So actually let's look at H star S. So S remember that S is the set of odd vertices and that is where this matching is done. So H star S is nothing but the optimal Hamiltonian cycle on that restricted graph. Okay, from our previous lema which I which is down here, we know that H star of S is less than H star of G. So we know that cost of is less than equal to cost of whatever G. So now let's look at just look at HR. Now we construct a matching. We take every other edge. You take this one, you would take this one, you take this one and and look at the alternate set also. So take this one and this one and this one. So look at the blue set and the red set. Since it's part of a Hamiltonian cycle, they're both matchings, right?

**[27:47]:** So let's call the red one M1 and the blue one M2. So I'm not saying they're perfect matchings. They're they're not the min minimum matchings, but they're definitely perfect matchings. And because they're because we know the perfect matching is M or the minimum matching is M. Cost of M is less than equal to cost of M1. And also the cost of M is less than equal to the cost of M2. Make sense? Because M was the minimum cost matching. you have cost of M is less than any other matching which is constructed from this again. So this implies that the cost of M is less than equal to half cost of okay let's not let's not write this here let's get a different board

**[28:54]:** this here so cost of H that's less than equal to half cost of M1 plus cost of M2. Since both of these guys are larger than this, their average is also larger than this. Right? But what is cost of M1 plus of M2? This is nothing but half cost of H star of S. Right? Because the Hamiltonian cycle is constructed from M1 and M2. So and by our lema this is less than equal to half cost of h star of g. Right? So now we have all we need. This is less than equal to half cost of h star of g. And then add them together you get cost of C dash is less than equal to cost of C is less than equal to the sum which is equal to three cost of H star of G.

**[30:09]:** So that's the proof. So there's a lot of lot lot of things going on here. Let's try to go back and see what we did. So we took a minimum spanning tree and then we tried to remove all the odd odd degree vertices. So we took all the odd degree vertices and made a perfect matching the minimum cost perfect matching. So we added edges just to make everything even degree. Then we took the oiler circuit on that graph and we removed duplicates. So that's fine. That's the easy part. But you took the oiler circuit on that graph. And then you argued that because all the circuit in that graph is just the sum of the edges in the spanning tree plus the sum of the edges in the matching which you added later. So the spanning tree had already bounded in the previous argument. The matching was bounded by taking the optimal Hamiltonian cycle decomposing it into two matchings arguing that those two matchings are not the optimal matching.

**[31:05]:** So not necessarily the optimal matchings but they're at least they're less than equal to the optimal. So there he went there. And so the cost of the optimal matching which you're using in our constructed path constructed Hamiltonian cycle is less than equal to both of these matchings. You add them up you get that bound and works. So questions on any of the steps. This is a lot of branching off and then coming back together but yeah yes that is not 3x3 that that would be P equals NP. Yeah. Anything else?

**[31:45]:** Okay, you're free to go or ask questions or whatever.

**[31:58]:** Oh,
