Signature classes of transportation polytopes

DOI10.1007/BF01580606MaRDI QIDQ689115zbMATHFDO

Authors Fred J. Rispoli, Michel Balinski

Publication date 9 December 1993

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

zbMATH Keywords

polytopestrongly polynomial algorithmdiameter of the dual polyhedronmonotonic Hirsch conjecturesignature algorithmstransportation problems

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• The Hirsch Conjecture for Dual Transportation Polyhedra
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• Proof of the Hirsch conjecture for a class of transportation polyhedra
• scientific article; zbMATH DE number 894763
• scientific article; zbMATH DE number 4172739

Cites work

• scientific article; zbMATH DE number 3630478 (Why is no real title available?)
• scientific article; zbMATH DE number 1768785 (Why is no real title available?)
• A competitive (dual) simplex method for the assignment problem
• A proof of the maximal diameter conjecture for the transportation polyhedron
• A relaxation column signature method for assignment problems
• Efficient dual simplex algorithms for the assignment problem
• Maximum matchings in bipartite graphs via strong spanning trees
• Paths on Polyhedra. I
• Signature Methods for the Assignment Problem
• Sparse dual transportation polyhedra: Extreme points and signatures
• The d-Step Conjecture and Its Relatives
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
• The monotonic diameter of the perfect matching and shortest path polytopes
• Transportation polytopes
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems

Cited in

(17)

• The monotonic diameter of the perfect matching and shortest path polytopes
• The Hirsch conjecture for the fractional stable set polytope
• A distributionally robust optimization approach for two-stage facility location problems
• Utility/privacy trade-off as regularized optimal transport
• Combinatoric classes of the transportation problem and their properties
• The hierarchy of circuit diameters and transportation polytopes
• Adjacency on combinatorial polyhedra
• Symmetric and Hankel-symmetric transportation polytopes
• On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows
• Convex integer maximization via Graver bases
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• The monotonic diameter of traveling salesman polytopes
• Obstructions to weak decomposability for simplicial polytopes
• \(N\)-fold integer programming
• On the closest point to the origin in transportation polytopes
• Plethysm and lattice point counting
• Graphs of transportation polytopes

This page was built for publication: Signature classes of transportation polytopes

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