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

DOI10.1007/BF00939806zbMath0662.90047MaRDI QIDQ1114587

Cornelis 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

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

Related Items (6)

Analysis of some interior point continuous trajectories for convex programming ⋮ A Polynomial Method of Weighted Centers for Convex Quadratic Programming ⋮ An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities ⋮ A survey of search directions in interior point methods for linear programming ⋮ A polynomial method of approximate centers for linear programming ⋮ On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A multiplicative barrier function method for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On the convexity of the multiplicative version of Karmarkar's potential function
• Karmarkar's linear programming algorithm and Newton's method
• An implementation of Karmarkar's algorithm for linear programming
• Search directions for interior linear-programming methods
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• 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

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