2008
Faster approximate lossy generalized flow via interior point algorithms
Daitch S, Spielman D. Faster approximate lossy generalized flow via interior point algorithms. 2008, 451-460. DOI: 10.1145/1374376.1374441.Peer-Reviewed Original ResearchInterior-point algorithmSymmetric M-matricesFlow problemLinear systemsPoint algorithmLinear equationsM-matrixGeneralized maximum flow problemMinimum cost flow problemLinear system solverFast approximation algorithmMaximum flow problemNumber of edgesRatios of integersDiagonally Dominant MatricesSystem solverΕ-approximationOptimal costApproximation algorithmFast algorithmParameter rangeMaximum flowEquationsPrevious algorithmsAlgorithm
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