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 (11)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Karmarkar's algorithm and the ellipsoid method