- Smoothed Analysis of Interior-Point Algorithms: Termination Daniel Spielman (spielmanmath.mit.edu) Shang-Hua Teng (stengcs.bu.edu) 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. Keywords: smoothed analysis, condition number, linear programming, interior-point methods Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: Download: [Postscript][PDF]Entry Submitted: 01/21/2003Entry Accepted: 01/21/2003Entry Last Modified: 01/21/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.