The ellipsoid method and its implications

DOI10.1007/BF01720281zbMath0504.90044MaRDI QIDQ1835842

Yanyan Li

Publication date: 1983

Published in: OR Spektrum (Search for Journal in Brave)

zbMATH Keywords

computational complexityhistorical developmentellipsoid method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst case behavior of the steepest edge simplex method
• On Khachian's algorithm and minimal ellipsoids
• Complexity of linear programming
• The ellipsoid method and its consequences in combinatorial optimization
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Khachiyan’s algorithm for linear programming
• Modifications and implementation of the ellipsoid algorithm for linear programming
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Matroid intersection algorithms
• On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid
• Dimensional Reduction Variant of the Ellipsoid Algorithm for Linear Programming Problems
• A bad network problem for the simplex method and other minimum cost flow algorithms
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities