2013
Spectral sparsification of graphs
Batson J, Spielman D, Srivastava N, Teng S. Spectral sparsification of graphs. Communications Of The ACM 2013, 56: 87-94. DOI: 10.1145/2492007.2492029.Peer-Reviewed Original ResearchSpectral sparsificationApproximate maximum flowLinear systemsSpectral approximationLinear time algorithmCombinatorial optimizationGraph sparsificationLinear equationsDominant matricesArbitrary graphsSparse graphsFast solutionUndirected networksFast algorithmDevelopment of algorithmsSparsificationMinimum cutMaximum flowGraphApproximationAlgorithmEquationsOptimizationImportant toolSolution
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