The Hirsch Conjecture for Dual Transportation Polyhedra

DOI10.1287/MOOR.9.4.629MaRDI QIDQ3220350zbMATH OpenOpenAlexWikidataFDO

Authors Michel Balinski

Publication date 1984

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://pure.iiasa.ac.at/id/eprint/2373/1/CP-83-009.pdf

zbMATH Keywords

combinatorial algorithmdual transportation polyhedronextreme pointsHirsch conjecture

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Proof of the Hirsch conjecture for a class of transportation polyhedra
• A proof of the Hirsch conjecture for one class of transportation polytopes
• A proof of the maximal diameter conjecture for the transportation polyhedron
• scientific article; zbMATH DE number 4087689
• On the circuit diameter of dual transportation polyhedra
• scientific article; zbMATH DE number 3861931
• Symmetric and Hankel-symmetric transportation polytopes
• scientific article; zbMATH DE number 1929288
• The Hirsch conjecture is true for (0,1)-polytopes
• scientific article; zbMATH DE number 3883948

Cited in

(26)

• The monotonic diameter of the perfect matching and shortest path polytopes
• Fenchel-type duality for matroid valuations
• Combinatoric classes of the transportation problem and their properties
• The hierarchy of circuit diameters and transportation polytopes
• A partial answer to the Demyanov-Ryabova conjecture
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• A relaxation column signature method for assignment problems
• Algorithms and codes for dense assignment problems: The state of the art
• Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
• Quadratic diameter bounds for dual network flow polyhedra
• Proof of the Hirsch conjecture for a class of transportation polyhedra
• On the length of simplex paths: The assignment case
• A competitive (dual) simplex method for the assignment problem
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• Topics of polyhedral combinatorics in transportation problems with exclusions
• The Hirsch conjecture for the fractional stable set polytope
• On the circuit diameter of some combinatorial polytopes
• Symmetric and Hankel-symmetric transportation polytopes
• A friendly smoothed analysis of the simplex method
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Signature classes of transportation polytopes
• On the shadow simplex method for curved polyhedra
• Asymptotic bounds on the combinatorial diameter of random polytopes
• An infeasible (exterior point) simplex algorithm for assignment problems
• Sparse dual transportation polyhedra: Extreme points and signatures
• Worst case examples of an exterior point algorithm for the assignment problem

This page was built for publication: The Hirsch Conjecture for Dual Transportation Polyhedra

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