Geometry of the Gass-Saaty parametric cost LP algorithm

DOI10.1007/BF02187776MaRDI QIDQ1825128zbMATH OpenOpenAlexFDO

Authors Victor Klee, Peter Kleinschmidt

Publication date 1990

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/131103

zbMATH Keywords

cyclingGass-Saaty algorithm

Mathematics Subject Classification ID

Linear programming (90C05)

Recommendations

• Parametric linear programming and anti-cycling pivoting rules
• Parametric programming and the primal-dual algorithm
• A practical anti-cycling procedure for linearly constrained optimization
• On Hoffman's celebrated cycling LP example
• On cycling in the simplex method of the transportation problem

Cites work

• scientific article; zbMATH DE number 3552183 (Why is no real title available?)
• scientific article; zbMATH DE number 3601415 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Computational complexity of parametric linear programming
• Higher Order Independence in Matroids
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• Stabbing line segments
• The Average number of pivot steps required by the Simplex-Method is polynomial

Cited in

(5)

• On polyhedral projection and parametric programming
• Degeneracy graphs: Theory and applications. An updated survey
• Encounters with degeneracy: A personal view
• On the existence of certain smooth toric varieties
• \(S\)-hypersimplices, pulling triangulations, and monotone paths

This page was built for publication: Geometry of the Gass-Saaty parametric cost LP algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825128)