2013
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
Spielman D, Teng S. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal On Computing 2013, 42: 1-26. DOI: 10.1137/080744888.Peer-Reviewed Original ResearchLinear time algorithmMassive graphsTime algorithmLinear system solverRunning timeSubset of verticesLinear systemsSpectral sparsifierLaplacian matrixNumber edgesSparsest cutSystem solverCorresponding eigenvectorsLocal clustering algorithmSmallest eigenvalueDominant matricesClustering algorithmPartitioning algorithmGraph partitioningWhole graphGraph algorithmsLocal algorithmGraphVerticesBetter clusters
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