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

2 Comments on “Prize Collecting Chinese Postman Problem”

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

  2. kevinwortman says:

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s