Tight integral duality gap in the Chinese postman problem

DOI10.1007/BF01581198zbMath0767.90088MaRDI QIDQ1196167

Ephraim Korach, Michal Penn

Publication date: 17 December 1992

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

zbMATH Keywords

\(T\)-joinchinese postmanintegral multicommodity flow\(T\)-cutintegral duality gapmaximum weight integral packingtight upper bound

Mathematics Subject Classification ID

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

Related Items

Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ On the integral 4-packing of \(T\)-cuts ⋮ Undirected distances and the postman-structure of graphs ⋮ Routing problems: A bibliography ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees ⋮ Tight integral duality gap in the Chinese postman problem ⋮ On shortest \(T\)-joins and packing \(T\)-cuts ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Vertex set partitions preserving conservativeness ⋮ A fast algorithm for maximum integral two-commodity flow in planar graphs

Cites Work

• Undirected distances and the postman-structure of graphs
• Matroids and multicommodity flows
• Tight integral duality gap in the Chinese postman problem
• The matroids with the max-flow min-cut property
• On the complexity of the disjoint paths problem
• On Odd Cuts and Plane Multicommodity Flows
• 2-Matchings and 2-covers of hypergraphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Matching, Euler tours and the Chinese postman
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item