The complexity of linear programming

DOI10.1111/j.1467-9574.1981.tb00717.xzbMath0469.90047OpenAlexW2017177415MaRDI QIDQ5904897

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

ellipsoid algorithmsimplex methodKhachiyan's algorithm

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

• Zufällige konvexe Polyeder im \(n\)-dimensionalen Euklidischen Raum
• Orientability of matroids
• Linear programming is log-space hard for P
• Efficient search for rationals
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the Structure of Polynomial Time Reducibility
• Two-Commodity Flow
• Paths, Trees, and Flowers
• How to Solve Linear Inequalities
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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