# Prize Collecting Chinese Postman Problem

**Posted:**July 19, 2012

**Filed under:**Available Project/Thesis Topics |

**Tags:**algorithms, graphs 2 Comments

The Chinese postman problem (CPP) is an NP-complete problem related to the traveling salesman problem (TSP). The desired output of TSP is the shortest cycle that visits every *vertex* exactly once. By contrast, the desired output of CPP is the shortest cycle that visits every *edge* at least once. The TSP corresponds to the problem of a visiting every city (vertex) only once; the CPP corresponds to visiting every city road (edge) at least once. By extension the CPP corresponds to the problem of traversing and photographing city roads to collect data for a street view service such as Google Street View or Microsoft Bing Maps.

In the prize collecting variant, every edge is assigned a numerical reward, and the object is the collect at least *X* points of reward. This corresponds to the (realistic) scenario in which some streets are more important than others, and the algorithm can choose to skip unimportant streets. The prize collecting CPP is NP-complete, but perhaps it could be approximated efficiently.

Project: design a polynomial time approximation scheme (PTAS) for the prize collecting Chinese postman problem.

For the non-prize-collecting variant…

1. Bisect every edge in the graph by the introduction of new nodes, mark these as ‘required’

2. Construct the minimum spanning tree of the new graph

3. A depth-first traversal of the tree will give you an order to visit ‘required’ nodes (aka roads), which is 2-competitive like the standard MST-TSP PTAS

As for the prize-collecting variant, I have a version that is polynomial, but it has no competitive guarantees.

Yes that is correct. This is meant to be a starting point for a student project, so let’s not spoil the fun for them too much. 🙂