We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A CENTERED PROJECTIVE ALGORITHM FOR LINEAR PROGRAMMING.
- Authors
Todd, Michael J.; Ye, Yinyu
- Abstract
We describe a projective algorithm for linear programming that shares features with Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in O(√nL) iterations like the latter methods. (Here n is the number of variables and L the input size of the problem.) However, it is motivated by seeking reductions in a suitable potential function as in projective algorithms, and the approximate centering is an automatic byproduct of our choice of potential function.
- Subjects
LINEAR programming; ALGORITHMS; TRAJECTORY optimization; MATHEMATICAL variables; MATHEMATICAL functions; PROBLEM solving
- Publication
Mathematics of Operations Research, 1990, Vol 15, Issue 3, p508
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.15.3.508