Unsolved
Smoothed Complexity of the Simplex Method
Posed by Spielman & Teng (implicit) (2004)
§ Problem Statement
Setup
Unsolved Problem
§ Discussion
Loading discussion…
§ Significance & Implications
§ Known Partial Results
§ References
[1]
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel Spielman, Shang-Hua Teng (2004)
Journal of the ACM
📍 Section 6.2 (“Further Analysis of the Simplex Algorithm”), first bullet (open question on analyzing other pivot rules under smoothed analysis), p. 460 (J. ACM 51(3):385–463).
[2]
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Daniel A. Spielman, Shang-Hua Teng (2001)
Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC)
📍 Section 1 (Introduction), Theorem 1.1 (polynomial smoothed complexity of the shadow vertex pivot rule), p. 296.