Matching, Euler Tours and the Chinese Postman I: The Convex Hull of Nonnegative Integer Parity Solutions Is the Polyhedron of Odd-Set InequalitiesResearch Paper
The Chinese postman problem, posed by Meigu Guan (Kwan Mei-Ko) in 1962, asks for a shortest closed walk in a graph that traverses every edge at least once: the route of a postman who must cover every street and return to the post office. It is the basic model of arc routing (street sweeping, snow ploughing, meter reading, inspection of networks), and it is…