Next: MINIMUM STACKER CRANE PROBLEM Up: Routing Problems Previous: MINIMUM CHINESE POSTMAN FOR Index

### MINIMUM K-CHINESE POSTMAN PROBLEM

- INSTANCE: Multigraph , initial vertex , length for each .

- SOLUTION: A collection of k cycles, each containing the initial vertex s, that collectively traverse every edge in the graph at least once.

- MEASURE: The maximum length of the k cycles.

- Good News: Approximable within 2-1/k [159].