UPDATING LOWER BOUNDS WHEN USING KARMARKAR PROJECTIVE ALGORITHM FOR LINEAR-PROGRAMMING

Authors
MITCHELL JE
Citation
Je. Mitchell, UPDATING LOWER BOUNDS WHEN USING KARMARKAR PROJECTIVE ALGORITHM FOR LINEAR-PROGRAMMING, Journal of optimization theory and applications, 78(1), 1993, pp. 127-142
Citations number
16
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science
Journal title
Journal of optimization theory and applications → ACNP
ISSN journal
00223239
Volume
78
Issue
1
Year of publication
1993
Pages
127 - 142
Database
ISI
SICI code
0022-3239(1993)78:1<127:ULBWUK>2.0.ZU;2-I
Abstract
We give two results related to Gonzaga's recent paper showing that low er bounds derived from the Todd-Burrell update can be obtained by solv ing a one-variable linear programming problem involving the centering direction and the affine direction. We show how these results may be u sed to update the primal solution when using the dual affine variant o f Karmarkar's algorithm. This leads to a dual projective algorithm.