0:07

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.

Â 2:43

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.

Â 4:50

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

Â 5:34

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.

Â 10:04

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.

Â 11:55

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.

Â