# 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.