Karmarkar's algorithm and the ellipsoid method

DOI10.1016/0167-6377(87)90016-2MaRDI QIDQ1095025zbMATH OpenOpenAlexFDO

Authors 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

ellipsoid methodpotential functionKarmarkar's algorithmprimal and dual programs

Mathematics Subject Classification ID

Linear programming (90C05)

Recommendations

• Interior point algorithm for linear programming problem and related inscribed ellipsoids
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• scientific article; zbMATH DE number 892328
• Containing and shrinking ellipsoids in the path-following algorithm
• scientific article; zbMATH DE number 3970513

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• An extension of Karmarkar's algorithm for linear programming using dual variables
• The Ellipsoid Method Generates Dual Variables

Cited in

(18)

• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• Eliminating columns in the simplex method for linear programming
• A deep cut ellipsoid algorithm for convex programming: Theory and applications
• Degeneracy in interior point methods for linear programming: A survey
• The steepest descent gravitational method for linear programming
• scientific article; zbMATH DE number 3727 (Why is no real title available?)
• Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A ``build-down scheme for linear programming
• An ellipsoid algorithm for the computation of fixed points
• Interior point algorithm for linear programming problem and related inscribed ellipsoids
• Containing and shrinking ellipsoids in the path-following algorithm
• Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem
• On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
• scientific article; zbMATH DE number 568568 (Why is no real title available?)
• scientific article; zbMATH DE number 3908161 (Why is no real title available?)
• A direct ellipsoid method for linear programming
• scientific article; zbMATH DE number 1310536 (Why is no real title available?)

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

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