Signature classes of transportation polytopes

DOI10.1007/BF01580606zbMath0783.90078MaRDI QIDQ689115

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

transportation problemspolytopestrongly polynomial algorithmdiameter of the dual polyhedronmonotonic Hirsch conjecturesignature algorithms

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)

Related Items (14)

On the closest point to the origin in transportation polytopes ⋮ Obstructions to weak decomposability for simplicial polytopes ⋮ A distributionally robust optimization approach for two-stage facility location problems ⋮ Utility/privacy trade-off as regularized optimal transport ⋮ The hierarchy of circuit diameters and transportation polytopes ⋮ The Hirsch conjecture for the fractional stable set polytope ⋮ \(N\)-fold integer programming ⋮ Plethysm and lattice point counting ⋮ The monotonic diameter of the perfect matching and shortest path polytopes ⋮ Convex integer maximization via Graver bases ⋮ On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows ⋮ The monotonic diameter of traveling salesman polytopes ⋮ Graphs of transportation polytopes ⋮ Adjacency on combinatorial polyhedra

Cites Work

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

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