Smoothed Analysis of Interior-Point Algorithms: Termination

Daniel A. Spielman, Shang-Hua Teng

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…