Smoothed analysis of termination of linear programming algorithms

We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng we show that the smoothed complexity of interior-point algorithms for linear programming is O(m³ log(m/σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m³ L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses.