Smoothed analysis of algorithms

DOI10.1145/990308.990310zbMath1192.90120OpenAlexW2034053794WikidataQ55952478 ScholiaQ55952478MaRDI QIDQ3583576

Daniel A. Spielman, Shang-Hua Teng

Publication date: 17 August 2010

Published in: Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits, Diffusive Influence Systems, Smoothed Analysis of Local Search Algorithms, Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem, On the enumeration of closures and environments with an application to random generation, Smoothed Analysis of the Successive Shortest Path Algorithm, A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Quantum machine learning: a classical perspective, Smoothing the Gap Between NP and ER, From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices, On Smoothed Analysis of Quicksort and Hoare’s Find, On the Condition Number of the Shifted Real Ginibre Ensemble, Branch-and-bound solves random binary IPs in poly\((n)\)-time, The smoothed number of Pareto-optimal solutions in bicriteria integer optimization, The Complexity of Diagonalization, Unnamed Item, The smallest singular value of a shifted random matrix, Learning a performance metric of Buchberger's algorithm, Why Greed Works for Shortest Common Superstring Problem, Nonparametric density estimation with nonuniform B-spline bases, Speeding up random walk mixing by starting from a uniform vertex, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, Relative Worst-Order Analysis: A Survey, Beyond the worst case: semi-random complexity analysis of winner determination, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Unnamed Item, On the smoothed analysis of the smallest singular value with discrete noise, Adversarial meta-learning of Gamma-minimax estimators that leverage prior knowledge, Complex random matrices have no real eigenvalues, Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs, RANDOM MATRICES: THE CIRCULAR LAW, A Friendly Smoothed Analysis of the Simplex Method, On percolation and ‐hardness, Improved smoothed analysis of multiobjective optimization, The probability that a slightly perturbed numerical analysis problem is difficult, Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise, Smoothed analysis of dynamic networks, Maximal unbordered factors of random strings, Smoothed analysis of balancing networks, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Mechanism design for perturbation stable combinatorial auctions, Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm, In Praise of Numerical Computation, The Effect of Adding Randomly Weighted Edges, Book Review: The basic George B. Dantzig, Fast Algorithms for Rank-1 Bimatrix Games, The Synchronizing Probability Function for Primitive Sets of Matrices, The conjugate gradient algorithm on a general class of spiked covariance matrices, Smooth analysis of the condition number and the least singular value, Geometric random edge, Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Decision-making based on approximate and smoothed Pareto curves, Smoothed analysis of binary search trees, Rank aggregation: new bounds for MCx, Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic, Mechanism design for policy routing, Smoothed analysis for tensor methods in unsupervised learning, Evaluating the quality of online optimization algorithms by discrete event simulation, Cycles and matchings in randomly perturbed digraphs and hypergraphs, From Parity and Payoff Games to Linear Programming, Communication complexity of approximate Nash equilibria, Analysis of FPTASes for the multi-objective shortest path problem, Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods, Bounds on the complexity of halfspace intersections when the bounded faces have small dimension, Asymptotic density, immunity and randomness, Smoothed analysis of complex conic condition numbers, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, The simultaneous semi-random model for TSP, Smoothed analysis of integer programming, Implementing the simplex method as a cutting-plane method, with a view to regularization, Nearly optimal minimax estimator for high-dimensional sparse linear regression, Running time of the treapsort algorithm, Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems, Smoothed Analysis on Connected Graphs, A probabilistic PTAS for shortest common superstring, Quantitative invertibility of random matrices: a combinatorial perspective, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Smoothed performance guarantees for local search, A quantization framework for smoothed analysis of Euclidean optimization problems, Smoothed heights of tries and patricia tries, Smoothed analysis of condition numbers and complexity implications for linear programming, Bounded-Degree Spanning Trees in Randomly Perturbed Graphs, Counting frequent patterns in large labeled graphs: a hypergraph-based approach, Bounds for the Convergence Time of Local Search in Scheduling Problems, On smoothed analysis of quicksort and Hoare's find, Phase transition of degeneracy in minor-closed families, Computational complexity of kernel-based density-ratio estimation: a condition number analysis, Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks, PASS approximation: a framework for analyzing and designing heuristics, Smoothed analysis of partitioning algorithms for Euclidean functionals, Halting time is predictable for large models: a universality property and average-case analysis, Learning with stochastic inputs and adversarial outputs, Mean width of random perturbations of random polytopes, A counterexample to the Hirsch conjecture, Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP, Recent development in computational complexity characterization of Nash equilibrium, Approximating independent set in perturbed graphs, On the Most Likely Voronoi Diagram and Nearest Neighbor Searching, The Smoothed Number of Pareto-Optimal Solutions in Non-integer Bicriteria Optimization, On realistic terrains, Robust smoothed analysis of a condition number for linear programming, MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability, A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization, Performance guarantees for scheduling algorithms under perturbed machine speeds, On the smoothness of paging algorithms, Lower Bounds for the Smoothed Number of Pareto Optimal Solutions, Convex hulls of perturbed random point sets, Relaxing the strong triadic closure problem for edge strength inference, Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes, Settling the Complexity of Local Max-Cut (Almost) Completely, George B. Dantzig and systems optimization, George Dantzig's impact on the theory of computation, The double pivot simplex method, The null space property for sparse recovery from multiple measurement vectors, \(k\)-means requires exponentially many iterations even in the plane, Quasi-decidability of a fragment of the first-order theory of real numbers, A new look at the automatic synthesis of linear ranking functions, Regional complexity analysis of algorithms for nonconvex smooth optimization, Nonlinear biobjective optimization: improving the upper envelope using feasible line segments, The isotropic constant of random polytopes with vertices on convex surfaces, Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem, On a condition number of general random polynomial systems, Random perturbation of sparse graphs, On the shadow simplex method for curved polyhedra, Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices, Bayesian incentive compatibility via matchings, Iterative computation of security strategies of matrix games with growing action set, Eigenvectors and controllability of non-Hermitian random matrices and directed graphs, Smoothed analysis for the conjugate gradient algorithm, Gaining traction: on the convergence of an inner approximation scheme for probability maximization, Algebraic Bayesian networks: checking backbone connectivity, Approximating the minimum independent dominating set in perturbed graphs, Fast quantum subroutines for the simplex method, Smoothed analysis of probabilistic roadmaps, Asymptotic density and computability, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Conditioning of random conic systems under a general family of input distributions, Column subset selection via sparse approximation of SVD, Computing in combinatorial optimization, Why greed works for shortest common superstring problem, Moser's shadow problem, Topology matters: smoothed competitiveness of metrical task systems, Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs, Optimizing MSE for clustering with balanced size constraints, Internet routing between autonomous systems: fast algorithms for path trading, Stabilize deep ResNet with a sharp scaling factor \(\tau\), On the efficiency of a randomized mirror descent algorithm in online optimization problems