An O(\(n\)) bound for the diameter of transshipment polytopes

DOI10.1016/0167-6377(92)90088-KzbMath0762.90082OpenAlexW2060807932MaRDI QIDQ1195869

Fred J. Rispoli

Publication date: 4 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90088-k

zbMATH Keywords

diameterHirsch conjecturecomplete directed graphtransshipment polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Unnamed Item
• The monotonic diameter of the perfect matching and shortest path polytopes
• Advantageous Properties of Dual Transhipment Polyhedra
• The d-Step Conjecture and Its Relatives
• A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem