On the average length of lexicographic paths

DOI10.1007/BF01580885zbMath0599.90076OpenAlexW2087817570MaRDI QIDQ3735459

Michel Balinski, A.-E. Nobs, Thomas M. Liebling

Publication date: 1986

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

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

zbMATH Keywords

complexitypolynomial algorithmdegeneraciesaverage lengthlexicographic pathrandomized simplex method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items

A note on degeneracy in linear programming, Post-optimality analysis of the optimal solution of a degenerate linear program using a pivoting algorithm, A new pivoting rule for solving various degeneracy problems, Selected bibliography on degeneracy, Degeneracy graphs: Theory and applications. An updated survey

Cites Work

• On the length of simplex paths: The assignment case
• A note on degeneracy in linear programming