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