Smoothed Analysis of Termination of Linear Programming Algorithms

Authors: Daniel A. Spielman, and Shang-Hua Teng .

Bibliographic Information: Mathematical Programming, Series B, Volume 97. July 2003.

To be presented at the 18th International Symposium on Mathematical Programming.

Abstract

We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} 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.

You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.

Daniel A. Spielman

Last modified: Thu Aug 7 14:25:25 EDT 2003