Smoothed Analysis of Interior-Point Algorithms: Termination

Details Smoothed Analysis of Interior-Point Algorithms: Termination Smoothed Analysis of Interior-Point Algorithms: Termination

2003-01-21

arxiv.org/abs/cs/0301019v1

Computer Science

Data Structures and Algorithms

to be presented at the 2003 International Symposium on Mathematical Programming

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Smoothed Analysis of Interior-Point Algorithms: Termination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Smoothed Analysis of Interior-Point Algorithms: Termination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smoothed Analysis of Interior-Point Algorithms: Termination will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-571132