Complexity of linear programming

DOI10.7916/D8TM7K45 10.1016/0167-6377(82)90047-5; 10.7916/D8TM7K45zbMath0486.90060OpenAlexW2159092483MaRDI QIDQ1165154

J. F. Traub, Henryk Woźniakowski

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90047-5

zbMATH Keywords

ellipsoid algorithmpolynomial-time algorithmlinear inequalitiesinteger modelmodels of computationcomplexity of linear programmingreal number models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Linear inequalities of matrices (15A39) Iterative numerical methods for linear systems (65F10)

Related Items

A survey of information-based complexity, On the complexity of quadratic programming in real number models of computation, Polynomial algorithms for linear programming over the algebraic numbers, Complexity of approximation problems, Computations over \(\mathbb{Z}\) and \(\mathbb{R}\): a comparison, Probabilistic analysis of a differential equation for linear programming, On average complexity of global optimization problems, Open questions in complexity theory for numerical optimization, Application of the ellipsoid method in an interactive procedure for multicriteria linear programming, On the probabilistic complexity of finding an approximate solution for linear programming, On the average number of steps of the simplex method of linear programming, Open problems in computational linear algebra, Information-based complexity: New questions for mathematicians, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, The ellipsoid method and its implications, Mathematical problems for the next century, Some aspects of studying an optimization or decision problem in different computational models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The great mathematical sputnik of 1979
• A new linear programming algorithm - better or worse than the simplex method?
• The ellipsoid method and its consequences in combinatorial optimization
• Khachiyan's linear programming algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Convergence and Complexity of Newton Iteration for Operator Equations
• Systems of distinct representatives and linear algebra
• How to Solve Linear Inequalities