Signature classes of transportation polytopes

DOI10.1007/BF01580606zbMATH Open0783.90078MaRDI QIDQ689115FDOQ689115

Authors: Fred J. Rispoli, Michel Balinski 

Publication date: 9 December 1993

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

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 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)

Cites Work

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

Cited In (17)

• On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows
• A distributionally robust optimization approach for two-stage facility location problems
• The monotonic diameter of the perfect matching and shortest path polytopes
• \(N\)-fold integer programming
• On the closest point to the origin in transportation polytopes
• Adjacency on combinatorial polyhedra
• Graphs of transportation polytopes
• The Hirsch conjecture for the fractional stable set polytope
• Combinatoric classes of the transportation problem and their properties
• Obstructions to weak decomposability for simplicial polytopes
• Utility/privacy trade-off as regularized optimal transport
• Symmetric and Hankel-symmetric transportation polytopes
• Transportation problems which can be solved by the use of hirsch-paths for the dual problems
• The monotonic diameter of traveling salesman polytopes
• Convex integer maximization via Graver bases
• Plethysm and lattice point counting
• The hierarchy of circuit diameters and 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)