On the worst case complexity of potential reduction algorithms for linear programming

MaRDI QIDQ1373761zbMATH OpenFDO

Authors Dimitris Bertsimas, X. Luo

Publication date 3 August 1998

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

interior point algorithmslower bounds on complexitypotential reduction algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• scientific article; zbMATH DE number 4197744
• scientific article; zbMATH DE number 1047677
• An infeasible-interior-point potential-reduction algorithm for linear programming
• On the Complexity of a Class of Projective Interior Point Methods

Cited in

(4)

• On lower bound updates in primal potential reduction methods for linear programming
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• On the length of primal-dual projection of potential reduction algorithm
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs

This page was built for publication: On the worst case complexity of potential reduction algorithms for linear programming

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