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.