A build-up variant of the logarithmic barrier method for LP

DOI10.1016/0167-6377(92)90104-BzbMath0757.90052OpenAlexW2058153952MaRDI QIDQ1200789

Dick den Hertog, Cornelis Roos, Tamás Terlaky

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90104-b

zbMATH Keywords

interior point methodpolynomial algorithmworst caselogarithmic barrier methodbuild-up variant

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A logarithmic barrier cutting plane method for convex programming, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, Polynomial Interior Point Cutting Plane Methods, Logarithmic Barrier Decomposition Methods for Semi-infinite Programming, A relaxed cutting plane method for semi-infinite semi-definite programming, Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming

Uses Software

• ACCPM

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A ``build-down scheme for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Cutting planes and column generation techniques with the projective algorithm
• Solving combinatorial optimization problems using Karmarkar's algorithm
• A polynomial method of approximate centers for linear programming
• A Potential Reduction Algorithm Allowing Column Generation
• A Complexity Reduction for the Long-Step Path-Following Algorithm for Linear Programming