The next problem for which we are going to design an approximation algorithm is the traveling salesman problem. More precisely, it is a special case called Metric TSP. So the word metric means that our input is an undirected graph whose edge weights on the negative and they satisfy the following triangle inequality. For any three vertices u, v and w, the distance from u to v was the distance from v to w is at least the distance from u to w. Okay, so for this graph, we need to find a cycle that visits each vertex exactly once and has minimum possible total length, okay? As with the case of vertex [INAUDIBLE], we are going to design an algorithm which is going to return in polynomial time a cycle which might not be optimal. But it is guaranteed to be at most twice as long as the optimal cycle. So we are going to return cycle C, whose length is at most two times the length of optimal cycle. Again, we do not know the value of OPT, but we're going to construct something which is at most two times OPT. Two times something the value of which we do not know. Again, we are going to do this by providing a good lower bound. So we're going to show that OPT is at least L for some value of L. And then we are going to show is that C is at most two times L. So what is the value L in our case? So we're going to use the minimum spanning tree as a lower bound for the optimal value of the traveling salesman cycle in the graph. So it is stated here in the lemma and the lemma says that for any undirected graph with non-negative traits. So in this case, we don't even need the graph to be metric. So for any such graph, the lengths of the minimum spanning tree is at most the lengths of the traveling salesman problem cycle in this graph. So why is that? This is just because, once again, if we can see the optimal cycle. So we discussed this already, assume that this is an optimal cycle. So the length of this cycle is equal to TSP of G, then let's return any edge from this cycle. Let me, just erase it. Okay, so we've just removed some edge. So what is left is some parts and it is in particular a spanning tree in this graph, right? It is some spanning tree. So it is a minimum spanning has total lengths, at most, the lengths of these parts. And these parts, since all edges are non-negative, these parts has length at most, the lengths of the traveling salesman cycle in this graph. So we get that the minimum spanning tree of G is at most the lengths of this parts. Let me denote it probably by P and P is at most TCP of G. We're now ready to present an approximate algorithm for the metric version of the traveling salesman problem based on the lower bounds that we've just discovered. So the first step is to construct the minimum spanning tree T of the graph G, okay? When it is constructed, we do the following, we double every edge in T and denote the results in graph by D. In the graph D, the degree of each vertex is even. So, there is a Eulerian cycle in this graph, so we find one and denote it by C, okay? And then finally, so the cycle C visits every edge of the graph D exactly once. In particular, it visits every vertex of our initial graph, but probably not just once. So we just remove duplicates from the sequence of vertices and return the resulting cycle. In other words, we return the sequence of vertices in order of the first appearance in the cycle C. So let me show you schematically how it works and then we will proceed to some concrete example. So assume that we have for example, just four vertices in our graph. So the first thing to do is to construct a minimum spanning tree in this graph. I assume that it looks as follows. The second step is to double every edge, let's do this. Now this graph is Eulerian. Namely the degree of this vertex is 2, the degree of this vertex is 2, the degree of this vertex is 2, the degree of this vertex is 6. This means that this graph contains an Eulerian cycle and we know already that an Eulerian cycle can be found in linear time. But in case when we have a tree whose each edge is doubled, this is particularly easy to find. So let me again schematically explain this to you. If we have a tree, let's consider this as a rooted tree. Assume that this was our tree. Here we have some subtrees and then we double every edge on this tree and also we double everything inside this subtrees. So how to construct in the Eulerian cycle in this double tree? Well, we can do this just recursively, we started the root, we then go into this subtree. And then we find an Eulerian cycle recursively in this subtree and then we get back using this edge. Then we go to the second subtree find an Eulerian cycle as it traverses all edges inside this subtree and then we will come back using this tree. Great, and then we proceed to the zero subtree find in Eu;erian cycle and get back. For example, for these three shown here in an Eulerian cycle will look like as follows. So let's start from this vertex, then we first traverse this edge. Then we traverse this edge. Then this edge. Then this one. Then this one and finally this one. So we've traversed all six edges. This is our cycle C. Now we need to return a cycle that visits every vertex in this graph. For this we are going to do the following. Let's start in the same vertex. We first use the same edge, then we use the second edge in our cycle C. But then the third edge in our cycle C visits the same vertex that was already visited. Instead of doing this, we go directly to vertex four. From this vertex, the fifth's edge of our cycle goes to the vertex which we already visited. So instead of doing this, we go to the initial vertex. So the metric property of our graph implies that instead of edges three and four, we use this just the direct edge from three to four. Then we can only decrease the total length of the resulting cycle. Okay, we now proceed to a more complete example. In this example, our vertices are just points on a plane. And we assume that the distance between two vertices is just the distance between the corresponding points on a plane. In this case of course, the edge weights or the edge distances satisfy the triangle inequality. So in this case, we're given then points which define implicitly a complete graph on end vertices. So the first thing to do is to construct a minimum spanning tree in this case. It looks as follows. Now with double every edge. Now it looks as follows and now we find an Eulerian cycle in the results in graph. For example, we start from this vertex and then we start traversing it like this. This is first one, the second one, the third one, the fourth one, the fifth one and so on. So 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 and we will count back to the initial vertex. Now, this cycle I'm sorry, visits this vertex for example several times and also this vertex several times. So what am I going to do. It's where I'm going to bypass some parts of this cycle. Namely, this is the final cycle that was constructed by our algorithm, let me show you how it was constructed. So from here we go to here because this vertex was not visited before. From here we go to here, from here we to go here. And from here we go to this vertex. But now, instead of using the fifth's edge, we go directly to this vertex. Because the fifth's edge visits the vertex that was already visited by our cycle. Then we go here because this vertex have not been visited before. Then we go here. Then we go here. And then again, instead of using the edge 10, 11, 12, 13 and so on, we go directly to the initial vertex. And now we visited all the edges. Okay, on the next slide we will prove that this algorithm is too approximate. Without proof is that the algorithm is too approximate. So this follows from three simple observations. First of all, the total length of the minimum spanning tree T is at most the optimum length of a traveling salesman cycle in our graph. So we proved this already. When we doubled each edge of the tree T, we get a graph whose total weight is at most to OPT, right? And then, when we transform this Eulerian cycle in this graph, into the Hamiltonian cycle. Namely into a cycle that visits each vertex exactly once. We can only decrease the total wait of this cycle. And at this point, we use essentially the fact the edge waits of our graph satisfies a triangle in equality. Namely when we replaced, if our Eulerian cycle goes as follows. And then we go directly from one vertex to the other, then we know for sure that the length of this edge is at most the sum of the lengths of all these edges. Because again, the lengths of edges in our graph satisfy triangle inequality. Let me conclude this part with a few remarks. First of all, it is known that the same version of the traveling salesman problem namely metric TSP can be approximate with the factor 1.5. The corresponding algorithm is known as Christofides' algorithm and it is actually the best known approximation to date. It is also interesting to note that the general version of this problem cannot be approximated within any polynomial time computable function if P is not equivalent to NP. In fact, if you design an algorithm that, for example, finds ten approximation for the general version of ten or n squared or even two to the n approximation for the general version. Then it can be used to solve the Hamiltonian cycle problem in polynomial time. If you design a good approximation algorithm for the traveling salesman problems and you solve in polynomial time also and as NP complete problem, which is actually related of course. There's a travelling salesman problem which is called Hamiltonian cycle problem. So if P is not equal to NP, then no good approximation for the general version is possible.