Technical Report CS0611

TR#:CS0611
Class:CS
Title: TIGHT INTEGRAL DUALITY GAP IN THE CHINESE POSTMAN PROBLEM
Authors: E. Korach and M. Penn
PDFCS0611.pdf
Abstract: Let G = (V, E) be a graph and a weight function w : E -+ Z+. Let T C 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 postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weight T-join and the maximum weighted integral packing of T-cut. This difference is called the (T-join)integral duality gap. Let nF be the number of components in the optimal T-join, Ttl) =minimum weight T-join and IItI) = max weight integral packing of T-cuts then we have T., -II., < nF -1. This result unifies and generalizes Fulkerson's result for ITI =2 and Seymour's result for ITI = 4. For a certain integral multicommodity flow problem in the plane, which was recently proved to be NP-complete, the above 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0611), 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 1990
To the main CS technical reports page

Computer science department, Technion
admin