Transportation problems which can be solved by the use of hirsch-paths for the dual problems

DOI10.1007/BF02591692zbMath0642.90070OpenAlexW2077760188MaRDI QIDQ3783840

Carl W. Lee, H. Schannath, Peter Kleinschmidt

Publication date: 1987

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02591692

zbMATH Keywords

average complexityassignment algorithmdual transportation polyhedraHirsch-conjectureprimal transportation problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)

Related Items

Utility/privacy trade-off as regularized optimal transport ⋮ Sparse dual transportation polyhedra: Extreme points and signatures ⋮ Worst case examples of an exterior point algorithm for the assignment problem ⋮ Signature classes of transportation polytopes ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ A strongly polynomial algorithm for the transportation problem ⋮ A relaxation column signature method for assignment problems ⋮ An infeasible (exterior point) simplex algorithm for assignment problems

Cites Work

• Unnamed Item
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The Hirsch Conjecture for Dual Transportation Polyhedra
• An algorithm for the assignment problem
• Efficient dual simplex algorithms for the assignment problem
• Signature Methods for the Assignment Problem
• A competitive (dual) simplex method for the assignment problem
• The d-Step Conjecture and Its Relatives
• Solving the Assignment Problem by Relaxation
• On some techniques useful for solution of transportation network problems