As we have discussed in the previous videos, the exact solutions that we currently have for the traveling salesman problem do not guarantee us any polynomial riding time. We currently do not have any algorithms that is guaranteed to produce an optimal solution in polynomial time say, in M squared, or M cubed or even M to the power one hundred. What we're going to do in this case is we're going to design an algorithm which is guaranteed to produce quickly a solution, which is at least twice longer than an optimal one. Such an algorithm is called two-approximate algorithm. First of all, it is important to mention that our algorithm only works or only guarantees to find a solution which is at most twice as longer, only for the metric version of the traveling salesman problem. In this case, first of all, the graph is undirected because the graph is symmetric. Meaning that for any two vertices, for any two nodes, we have the weight of the edge U,V is equal to the weight of the edge V,U. And also what is probably more important is that all the weight should satisfy the triangle inequality. For any three nodes, U, V and Z, the weight of the edge U,V is at most the sum of the edges U, Z and Z,V. Going from U to V through the node Z could not be shorter than going directly from U to V. In particular, the Euclicean TCP is also metric TCP. The Euclicean distances satisfies the triangle inequality. What are we going to do for the metric? The TSP is to design a very efficient algorithm that is going to produce a cycle quickly and is going to work even on instances in practice where is like using millions of neurons. But the solution is not guaranteed to be optimal at the same time it is guaranteed to be at most two times longer than an optimal one. And this says once again called an approximation algorithm. First of all, let me remind you that for a non-directed graph, we know that this is the weight of the Minimum Spanning Tree is at most the length of the optimal traveling salesman person cycle in this graph. This is true not only for metric graphs but for any graph. The reason is simple, if we consider an optimal cycling in this graph, it looks somehow like this and then we remove some edge from this graph, for example this one. Then, what is left is actually some spanning tree in this graph. Why does it tree? Well, this is just a path and the path is a special case of a tree. This is just the non edged tree. This is some tree and it's weight is at least of the weight of the minimal spanning tree. The minimum spanning tree is the minimum one. The weight of this parts is at least the weight of the minimum spanning tree which finally proves that the weight of the optimal cycle of the travelling salesman. Person in the graph is at least the minimum spanning tree. Then we're ready to present an algorithm. We first construct the minimum spanning tree of G. Recall that this tree can be done very efficiently in time almost linear in the number of nodes and edges in the input graph. Then we do the following strange trick, we double every edge in T and the nodes are resulting. the resulting graph is the results and set of the edges by D. Then, what we see and we will see this now on a small example is that the results in the graph is Eulerian so in this graph we can find an Eulerian cycle. This cycle visits all the edges that we currently have in our graph D. Then what we do is we just return a cycle that is obtained from this cycle found in D by removing all the repeated nodes. Let me explain all the details of this algorithm as usual on a point example. I assume that we have several points of the plane and the edges between these points are just distances between them on a plane so this is definitely a metric case. We first construct the minimum spanning tree. In this particular case, it looks somehow like this. Then we double every edge. This is a very simple operation so we just replace every edge with two copies of the same action. We assume that the average size edge just has the same length. They are shown like this only for visualizing that they are indeed double. Now, what we see here is that the degree of every node here is even. Which means that the resulting graph is Eulerian. There is a cycle that visits every edge not every node but every edge exactly once. We can easily find such a cycle. We can either construct an Eulerian cycle and for these double trees. This is particularly easy actually because we can use one of the vertices as a root and then we recursively first traverse one sub-trees and the second sub-trees and so on. In any case, we can construct an Eulerian cycle in the graph somehow and it can be done very efficiently. Let's consider one such cycle. For example, we first draw here, then here, then here, then here, here and so on. We finally traverse all the edges in our graph. Then we do a very simple operation. We assume that we now need to transform the cycle into a cycle that visits every node exactly once. Currently, it visits some of the nodes more than once. Then we do the following, let me use a different color for them. We first go to these nodes then we go to these nodes, following our Eulerian cycle. Then we go to these node. Then we go to these node. Then our Eulerian cycle using the edge number of five returns to these nodes that we already visited. In order to by pass this, we do not return here but we go to the next vertex. Instead of going using edges five and six, we go directly from here to here. And it's a nice property, is that our graph is metric. Which means that going directly from this node to this node, can only shorten our current cycle. Using this edge instead of edges five and six can only decrease the length of our current cycle. Then we repeat during the following thing. We follow the edge seven then we follow the edge 8 then we follow the edge nine and then our Eulerian cycle returns to the nodes that we visited already then to this node, to that node, to that node so we skip all these nodes and we return just directly to the initial node. What we get as a result is a cycle like this one. We've almost proved already that this algorithm is too approximate. Let's now state this formally. The algorithm is too approximate and once again, this means that it is guaranteed to return a solution which is at most twice longer than an optimal one. It is also very efficient. It works in time almost linear in the size of our graph. Because finding an Eulerian cycle can be done in linear time and finding the minimum spanning tree, can also be done almost in linear time, in time something like. Now let's prove so we already know that the weight of the minimum spanning tree is at most the weight of the optimal solution which means that when we double every edge of our graph, we get the set of edges whose total weight is at most two times optimum often. At the last stage, I'm sorry, of our algorithm, we do some bypasses of our cycle and since our instances metrics, we can only shorten the length of our cycle at this point. Which finally proves that this algorithm is too approximate. Now, as the concluding remark, let me mention that this algorithm can be actually improved to give a guarantee or 1.5. This is known as the Christofides algorithm. In this algorithm instead of doubling every edge, we actually find a perfect match on edges off or degree in this tree and then we actually repeat actually the same procedure. A better approximation factor is known, this factor s 1.5 and it is actually the best one. It was presented by at Christofides in something like 77 so many years ago and it has not been improved since then. Let me also mention another interesting fact so assuming that P is not equal to NP, assuming that for the general version of the traveling salesman person, there is no algorithm that guarantees an approximation alpha for any constant alpha and even not constant alpha. For the general version of TSP, we currently do not have any hopes for getting good approximations. Roughly this happens because if we had such an approximation algorithm then we would be able to solve the [inaudible] cycle problem also in polynomial time but this would mean that P is equal to NP.
