On adaptive-step primal-dual interior-point algorithms for linear programming

The authors 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. They 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.