Complexity of linear programming

DOI10.1016/0167-6377(82)90047-5MaRDI QIDQ1165154zbMATH OpenOpenAlexFDO

Authors J. F. Traub, H. 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

linear inequalitiespolynomial-time algorithminteger modelmodels of computationellipsoid algorithmcomplexity of linear programmingreal number models

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• A new linear programming algorithm - better or worse than the simplex method?
• Convergence and Complexity of Newton Iteration for Operator Equations
• How to Solve Linear Inequalities
• Khachiyan's linear programming algorithm
• Systems of distinct representatives and linear algebra
• The ellipsoid method and its consequences in combinatorial optimization
• The great mathematical sputnik of 1979
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(17)

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

This page was built for publication: Complexity of linear programming

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