Smoothed Analysis of Interior-Point Algorithms: Termination
<|reference_start|>Smoothed Analysis of Interior-Point Algorithms: Termination: 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.<|reference_end|>
@article{spielman2003smoothed,
    title={Smoothed Analysis of Interior-Point Algorithms: Termination},
    author={Daniel A. Spielman and Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0301019},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0301019},
    primaryClass={cs.DS}
}