Smoothed analysis of algorithms

DOI10.1145/380752.380813zbMath1323.68636WikidataQ56228654 ScholiaQ56228654MaRDI QIDQ5175982

Shang-Hua Teng, Daniel A. Spielman

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380813

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

90C60: Abstract computational complexity for mathematical programming problems

Related Items

The interior-point revolution in optimization: History, recent developments, and lasting consequences, The diameter of randomly perturbed digraphs and some applications, Random knapsack in expected polynomial time, Expansion and Lack Thereof in Randomly Perturbed Graphs, Running time of the treapsort algorithm, Approximation bounds for sparse principal component analysis, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Core instances for testing: a case study, Probabilistic analysis of complex Gaussian elimination without pivoting, On the Complexity of the Metric TSP under Stability Considerations, A Probabilistic PTAS for Shortest Common Superstring, On smoothed analysis in dense graphs and formulas, How many random edges make a dense hypergraph non-2-colorable?, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)