TR#: | CS0611 |

Class: | CS |

Title: | TIGHT INTEGRAL DUALITY GAP IN THE CHINESE POSTMAN PROBLEM |

Authors: | E. Korach and M. Penn |

CS0611.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. |

Copyright | The 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