The complexity of linear programming

DOI10.1111/J.1467-9574.1981.TB00717.XMaRDI QIDQ5904897zbMATH OpenOpenAlexFDO

Authors Alexander H. G. Rinnooy Kan, Jan Telgen

Publication date 1981

Published in Statistica Neerlandica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/j.1467-9574.1981.tb00717.x

zbMATH Keywords

simplex methodellipsoid algorithmKhachiyan's algorithm

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3744912 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3197060 (Why is no real title available?)
• Efficient search for rationals
• How to Solve Linear Inequalities
• Linear programming is log-space hard for P
• On the Structure of Polynomial Time Reducibility
• Orientability of matroids
• Paths, Trees, and Flowers
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Two-Commodity Flow
• Zufällige konvexe Polyeder im \(n\)-dimensionalen Euklidischen Raum

Cited in

(3)

• The Average number of pivot steps required by the Simplex-Method is polynomial
• On relaxation methods for systems of linear inequalities
• A space decomposition-based deterministic algorithm for solving linear optimization problems

This page was built for publication: The complexity of linear programming

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