On the length of simplex paths: The assignment case

DOI10.1007/BF02591931zbMath0577.90048OpenAlexW1988237808MaRDI QIDQ3698637

Snjólfur Ólafsson, Per Olov Lindberg

Publication date: 1984

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

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

zbMATH Keywords

polynomial growthoptimal assignment problemnumber of pivotslength of simplex paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (4)

On the length of simplex paths: The assignment case ⋮ Affirmative action algorithms ⋮ On the average length of lexicographic paths ⋮ The monotonic diameter of the perfect matching and shortest path polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• The Hirsch Conjecture for Dual Transportation Polyhedra
• On the length of simplex paths: The assignment case
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Some experiments with the pathological linear programs of N. Zadeh
• Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
• A bad network problem for the simplex method and other minimum cost flow algorithms
• ZufÄllige konvexe Polygone in einem Ringgebiet
• Some results in probabilistic geometry
• How to Solve Linear Inequalities

This page was built for publication: On the length of simplex paths: The assignment case