We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.
No takes yet. Share an insight, caveat, or question.
Mizuno et al. (1993) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: