Smoothed analysis of algorithms
From MaRDI portal
Publication:5175982
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
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, 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