New trajectory-following polynomial-time algorithm for linear programming problems

DOI10.1007/BF00939806MaRDI QIDQ1114587zbMATH OpenFDO

Authors C. Roos

Publication date 1989

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

zbMATH Keywords

interior point methodpath following methodspolynomial time bound

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal projective interior point method for linear programming
• scientific article; zbMATH DE number 938987
• Interior path following primal-dual algorithms. I: Linear programming

Cites work

• scientific article; zbMATH DE number 4164543 (Why is no real title available?)
• scientific article; zbMATH DE number 3809326 (Why is no real title available?)
• scientific article; zbMATH DE number 4048535 (Why is no real title available?)
• scientific article; zbMATH DE number 3253619 (Why is no real title available?)
• scientific article; zbMATH DE number 3381785 (Why is no real title available?)
• A modification of Karmarkar's linear programming algorithm
• A multiplicative barrier function method for linear programming
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• An implementation of Karmarkar's algorithm for linear programming
• Karmarkar's linear programming algorithm and Newton's method
• On the convexity of the multiplicative version of Karmarkar's potential function
• Search directions for interior linear-programming methods
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry

Cited in

(13)

• Following a “Balanced” Trajectory from an Infeasible Point to an Optimal Linear Programming Solution with a Polynomial-Time Algorithm
• Algorithmic Enhancements to the Method of Centers for Linear Programming Problems
• An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
• Analysis of some interior point continuous trajectories for convex programming
• Volumetric path following algorithms for linear programming
• New interior point algorithms in linear programming
• On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
• A Polynomial Method of Weighted Centers for Convex Quadratic Programming
• A survey of search directions in interior point methods for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An interior point continuous path-following trajectory for linear programming
• scientific article; zbMATH DE number 5066284 (Why is no real title available?)
• A polynomial method of approximate centers for linear programming

This page was built for publication: New trajectory-following polynomial-time algorithm for linear programming problems

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