Optimization Online


Smoothed Analysis of Interior-Point Algorithms: Termination

Daniel Spielman (spielman***at***math.mit.edu)
Shang-Hua Teng (steng***at***cs.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 )


Download: [Postscript][PDF]

Entry Submitted: 01/21/2003
Entry Accepted: 01/21/2003
Entry Last Modified: 01/21/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society