Dominik Farhan

Chinese postman and Travelling salesman problems

Chinese Postman Problem

Find a path that goes through each edge and returns.

If GG is connected with and all vertices have even degree than clearly we can find an Eulerian path that solves the problem. How? Observe that GG must be a edge-disjoint union of cycles. We can find all these cycles and create the Eulerian tour.

What is GG has vertice of odd length? Then postman must travel multiple times through some edges. We will show that the postman does not need to travel one edge more than two times. The idea is that on one side he travels everything he need, then he goes through the edge, delivers everything on the other side and returns.

Definition (T-set). T={v∈V∣deg(v) is odd}T = \{ v\in V \mid deg(v) \text{ is odd}\}
Definition (T-join).

E′⊆EE' \subseteq E is T-join if GT(V,E′)G_T(V, E') satisfies that: degGT(v)deg_{G_T}(v) is odd iff v∈Tv\in T..

We do the followin observation: Let E′⊆E' \subseteq be the set of edges that must be traveled more than once. Then these edges are traveled twice and (V,E′)(V, E') is minimal T-join.

Hence, to solve CPP, we can find the minimal T-join.

The idea is the following: Take a complete graph on TT and function w:(T2)→Q+w: {T \choose 2} \rightarrow \mathbb{Q}^+ where w(uv)w(uv) is the length of the corresponding shortest path in GG.

Let MM be perfect matching of the complete graph with minimal weight. Let p(uv)p(uv) be the shorted path in GG for any two vertices in TT. Now when we take ∪e∈Mp(e)\cup_{e \in M} p(e) we claim it is a T-join.

Why? All vertices in TT are first/last vertex of some path in the union, hence their degree is odd. It is also minimal. Why? Let there be another E′E' T-join. Then becuase each vertex of TT must be in G[E′]G[E'] with an odd degree, we can parition E′E' into some paths in the complete graph. This gives us perfect matching. But we know, that the previous MM was minimal so the previous T-join was minimal.

Travelling Salesman Problem

Find a graph traversal of minimal length that visits each vertex and returns to the original. Known to be NP-complete.

We will also assume:

Note that the general TSP cannot be aproximated: when all edges have weights zero any approximation that is kk-times worse still needs to find soltuion with weight 00. Thus this would solve the Hamiltonian cycle problem which there is no known fast algorithm.

22-OPT

Using minimal spanning tree.

We find a minimal spanning tree, start in arbitrary vertex and take each edge two times. We can improve it by never visiting vertex twice and by the triangle inequality always jump directly to the following vertex.

We know that the minimal spanning tree gives u lower bound on OPT. We can show this by taking the optimal solution ad removing one edge from it. Surely we get a spanning tree which cannot be of smaller weight than the minimal. Therefore surely this algorithms is 22-OPT.

Christofides heuristic

This improves on the previus approach by not taking edges two times. The realization is that only when a vertex is of odd degree there is an edge adjacent to it that we traverse two times.

Let SS be set of all vertices with odd degree in the spanning tree. Let MM be minimal matching of these vertices. We claim that M∪˙TM \dot{\cup} T where TT are edges in the minimal spanning tree, is 3/23/2 optimal. We already know that edges in the minimal spanning tree give the lowev bound to optimum. For the matching, observe that by the handshaking lemma there is a even number of vertices in SS. We can use the matching to get a cycle. This cycle contains at most all VV vertices and from the triangle inequality we get that its weight is bounded by OPT and because we are taking cheaper part of it, we can conclude that the cost of the matching is at most 1/21/2-OPT. Combining this together we get that 3/23/2-OPT algorithm.

We can further improve the previous result by finding an eulerian tour in the multigraph and removing repeated vertices similarly to what we we did in the spanning tree algorithm.