Karmarkar's algorithm and the ellipsoid method

DOI10.1016/0167-6377(87)90016-2zbMath0631.90035OpenAlexW2061711344MaRDI QIDQ1095025

Yinyu Ye

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0167-6377(87)90016-2

zbMATH Keywords

potential functionellipsoid methodKarmarkar's algorithmprimal and dual programs

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items

A direct ellipsoid method for linear programming, Eliminating columns in the simplex method for linear programming, Polynomial time algorithms for some classes of constrained nonconvex quadratic problems, A ``build-down scheme for linear programming, On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm, Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem, The steepest descent gravitational method for linear programming, Containing and shrinking ellipsoids in the path-following algorithm, Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method, Degeneracy in interior point methods for linear programming: A survey, A deep cut ellipsoid algorithm for convex programming: Theory and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• The Ellipsoid Method Generates Dual Variables
• A variant of Karmarkar's linear programming algorithm for problems in standard form