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 (http://arxiv.org/abs/cs.DS/0302011) 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. Received: December 10, 2002 / Accepted: April 28, 2003 Published online: June 5, 2003 Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25