Tight integral duality gap in the Chinese postman problem

DOI10.1007/BF01581198MaRDI QIDQ1196167zbMATH OpenFDO

Authors Ephraim Korach, Michal Penn

Publication date 17 December 1992

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01581198

zbMATH Keywords

\(T\)-cut\(T\)-joinchinese postmanintegral duality gapintegral multicommodity flowmaximum weight integral packingtight upper bound

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Review text

Let \(G=(V,E)\) be a graph and let \(w\) be a weight function \(w:E\to Z^ +\). Let \(T\subseteq 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 weight integral packing of \(T\)-cuts. This difference is called the \((T\)-join) integral duality gap. Let \(\tau_ w\) be the minimum weight of a \(T\)-join, and let \(\nu_ w\) be the maximum weight of an integral packing of \(T\)-cuts. If \(F\) is a non-empty minimum weight \(T\)-join, and \(n_ F\) is the number of components of \(F\), then we prove that \(\tau_ w-\nu_ w\leq n_ F- 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, 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.

Recommendations

• scientific article; zbMATH DE number 16725
• On the integral 4-packing of \(T\)-cuts
• A quick proof of Seymour's theorem on t-joins
• scientific article; zbMATH DE number 4211828
• Two-trees optimal \(T\)-join and integral packing of \(T\)-cuts

Cites work

• 2-Matchings and 2-covers of hypergraphs
• Graph theory with applications
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3290885 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• Matroids and multicommodity flows
• On Odd Cuts and Plane Multicommodity Flows
• On the complexity of the disjoint paths problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• The matroids with the max-flow min-cut property
• Tight integral duality gap in the Chinese postman problem
• Undirected distances and the postman-structure of graphs

Cited in

(14)

• Undirected distances and the postman-structure of graphs
• Tight integral duality gap in the Chinese postman problem
• On shortest T-joins and packing T-cuts
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Vertex set partitions preserving conservativeness
• On the integral 4-packing of \(T\)-cuts
• Routing problems: A bibliography
• On complexity, representation and approximation of integral multicommodity flows
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• Finding thet-join structure of graphs
• scientific article; zbMATH DE number 16725 (Why is no real title available?)
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Primal-dual approximation algorithms for integral flow and multicut in trees

This page was built for publication: Tight integral duality gap in the Chinese postman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196167)