#
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