Prize Collecting Chinese Postman Problem

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.

Advertisements