2005
Improved Smoothed Analysis of the Shadow Vertex Simplex Method
Deshpande A, Spielman D. Improved Smoothed Analysis of the Shadow Vertex Simplex Method. 2005, 349-356. DOI: 10.1109/sfcs.2005.44.Peer-Reviewed Original ResearchSmoothed complexityShadow vertex simplex methodParameter of perturbationNumber of constraintsSmoothed analysisGeometric resultsNumber of variablesLinear programVertex methodLinear programmingSimple proofSimplex methodRunning timeMultiplicative factorExponentSpielmanPolytopeProofComplexityVerticesPerturbations
2003
Smoothed analysis of termination of linear programming algorithms
Spielman D, Teng S. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming 2003, 97: 375-404. DOI: 10.1007/s10107-003-0448-9.Peer-Reviewed Original ResearchSmoothed Analysis
Spielman D, Teng S. Smoothed Analysis. Lecture Notes In Computer Science 2003, 2748: 256-270. DOI: 10.1007/978-3-540-45078-8_23.Peer-Reviewed Original Research