ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING

Authors
MIZUNO S TODD MJ YE YY
Citation
S. Mizuno et al., ON ADAPTIVE-STEP PRIMAL-DUAL INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING, Mathematics of operations research, 18(4), 1993, pp. 964-981
Citations number
31
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
18
Issue
4
Year of publication
1993
Pages
964 - 981
Database
ISI
SICI code
0364-765X(1993)18:4<964:OAPIAF>2.0.ZU;2-G
Abstract
We describe several adaptive-step primal-dual interior point algorithm s for linear programming. All have polynomial time complexity while so me allow very long steps in favorable circumstances. We provide heuris tic reasoning for expecting that the algorithms will perform much bett er in practice than guaranteed by the worst-case estimates, based on a n analysis using a nonrigorous probabilistic assumption.