Smoothed analysis of algorithms

DOI10.1145/380752.380813zbMath1323.68636OpenAlexW2118625817WikidataQ56228654 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

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (25)

Conflict-driven satisfiability for theory combination: lemmas, modules, and proofs ⋮ The diameter of randomly perturbed digraphs and some applications ⋮ A Probabilistic PTAS for Shortest Common Superstring ⋮ The interior-point revolution in optimization: History, recent developments, and lasting consequences ⋮ Running time of the treapsort algorithm ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time ⋮ Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices ⋮ How many random edges make a dense hypergraph non-2-colorable? ⋮ Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ The least singular value of a random symmetric matrix ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling ⋮ Approximation bounds for sparse principal component analysis ⋮ The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic ⋮ 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 ⋮ Random knapsack in expected polynomial time ⋮ On the Complexity of the Metric TSP under Stability Considerations ⋮ Unnamed Item ⋮ Smoothed analysis for the conjugate gradient algorithm ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Probabilistic analysis of complex Gaussian elimination without pivoting ⋮ On smoothed analysis in dense graphs and formulas

Cites Work

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

This page was built for publication: Smoothed analysis of algorithms