Technical Report CS0521

Title: Tight Integral Duality Gap in the Chinese Postman Problem
Authors: E. Korach and M. Penn
Abstract: Let G=(V,E) be a graph and a weight function w: E->Z+. Let T contained-in V be an even subset of the vertices of G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. A T-join is a minimal subset of edges that meets every T-cut (a generalization of solutions to the Chinese postnan problem). The main theorem of this paper gives a tight upper bound on the integral duality gap. That is to say, a bound on the difference between the minimum weight T-join and the maximum weighted integral packing of T-cuts. This theorem is proved algorithmically. Let nF be the number of components in the optimal T-join, tw = minimum weight T-join and vw= max weight integral packing of T-cuts then we have t2-vw<=nF-1. This result unifies and generalizes Fulkerson's result for |T|=2 and Seymour's result for |T|=4. For a certain integral multicommodity flow problem in the plane, the above algorithmic result gives a solution such that for every commodity the flow is less than the demand by at most one unit.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion