Smoothed Analysis of Interior-Point Algorithms: Termination
| dc.creator | Spielman, Daniel A. | |
| dc.creator | Teng, Shang-Hua | |
| dc.date | 2003-01-21 | |
| dc.date.accessioned | 2026-07-07T03:19:22Z | |
| dc.date.available | 2026-07-07T03:19:22Z | |
| dc.description | 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/σ))$. 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. | |
| dc.description | to be presented at the 2003 International Symposium on Mathematical Programming | |
| dc.identifier | https://arxiv.org/abs/cs/0301019 | |
| dc.identifier | http://arxiv.org/abs/cs/0301019 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31432 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.1; G.1.6 | |
| dc.title | Smoothed Analysis of Interior-Point Algorithms: Termination | |
| dc.type | text |