0:00

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.

Â