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

DOI10.1007/BF02591692zbMath0642.90070MaRDI QIDQ3783840

Carl W. Lee, Peter Kleinschmidt, H. Schannath

Publication date: 1987

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

zbMATH Keywords

average complexity; assignment algorithm; dual transportation polyhedra; Hirsch-conjecture; primal transportation problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

90C27: Combinatorial optimization

Related Items

Signature classes of transportation 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, 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

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