MINIMUM K-CHINESE POSTMAN PROBLEM

• INSTANCE: Multigraph $G=\left(V,E\right)$, initial vertex $s\in V$, length $l(e)\in N$ for each $e\in E$.

• 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 [171].