2006
Smoothed Analysis of Algorithms and Heuristics
Spielman D, Teng S. Smoothed Analysis of Algorithms and Heuristics. 2006, 274-342. DOI: 10.1017/cbo9780511721571.010.Peer-Reviewed Original ResearchSmoothed analysisAnalysis of algorithmsNumber of iterationsMathematical programmingCombinatorial optimizationComputational geometryApproximation algorithmIterative algorithmApproximation ratioRandomized algorithmDiscrete inputsPerturbation modelRandom bitsScientific computingError probabilityTime complexityCompetitive ratioNumber of callsAlgorithmOnline algorithmNumber of bitsOpen questionHeuristicsIterationComputation
2005
The Smoothed Analysis of Algorithms
Spielman D. The Smoothed Analysis of Algorithms. Lecture Notes In Computer Science 2005, 3623: 17-18. DOI: 10.1007/11537311_2.Peer-Reviewed Original ResearchSmoothed analysisImproved 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
2004
Smoothed analysis of algorithms
Spielman D, Teng S. Smoothed analysis of algorithms. Journal Of The ACM 2004, 51: 385-463. DOI: 10.1145/990308.990310.Peer-Reviewed Original Research
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