Smoothed analysis of algorithms

DOI10.1145/990308.990310zbMATH Open1192.90120DBLPjournals/jacm/SpielmanT04OpenAlexW2034053794WikidataQ55952478 ScholiaQ55952478MaRDI QIDQ3583576FDOQ3583576

Authors: 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

Recommendations

• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Fundamentals of Computation Theory
• Smoothed analysis of algorithms and heuristics: progress and open questions
• scientific article; zbMATH DE number 1962932
• Smoothed Analysis of the Simplex Method
• A friendly smoothed analysis of the simplex method
• A friendly smoothed analysis of the simplex method
• Smoothed analysis of condition numbers and complexity implications for linear programming
• On the smoothed complexity of convex hulls

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Complex random matrices have no real eigenvalues
• Stabilize deep ResNet with a sharp scaling factor \(\tau\)
• Moser's shadow problem
• Quantitative invertibility of random matrices: a combinatorial perspective
• Optimizing MSE for clustering with balanced size constraints
• Why Greed Works for Shortest Common Superstring Problem
• On smoothed analysis of quicksort and Hoare's find
• Internet routing between autonomous systems: fast algorithms for path trading
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• Mechanism design for perturbation stable combinatorial auctions
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Rank aggregation: new bounds for MCx
• A friendly smoothed analysis of the simplex method
• Regional complexity analysis of algorithms for nonconvex smooth optimization
• Nonlinear biobjective optimization: improving the upper envelope using feasible line segments
• Smoothed analysis for tensor methods in unsupervised learning
• On the smoothed analysis of the smallest singular value with discrete noise
• Evaluating the quality of online optimization algorithms by discrete event simulation
• Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
• On the Condition Number of the Shifted Real Ginibre Ensemble
• Analysis of FPTASes for the multi-objective shortest path problem
• Bounds for the convergence time of local search in scheduling problems
• Asymptotic density, immunity and randomness
• Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem
• Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
• Gaining traction: on the convergence of an inner approximation scheme for probability maximization
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• Algebraic Bayesian networks: checking backbone connectivity
• Relative Worst-Order Analysis: A Survey
• The simultaneous semi-random model for TSP
• Smoothed Analysis of Integer Programming
• Quantum machine learning: a classical perspective
• Fast quantum subroutines for the simplex method
• On Smoothed Analysis of Quicksort and Hoare’s Find
• Iterative computation of security strategies of matrix games with growing action set
• The effect of adding randomly weighted edges
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
• Smoothed analysis of the successive shortest path algorithm
• Asymptotic density and computability
• PASS approximation: a framework for analyzing and designing heuristics
• Computing in combinatorial optimization
• Beyond the worst case: semi-random complexity analysis of winner determination
• Title not available (Why is that?)
• A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
• Random perturbation of sparse graphs
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Improved smoothed analysis of multiobjective optimization
• Counting frequent patterns in large labeled graphs: a hypergraph-based approach
• Smoothed complexity theory
• Maximal unbordered factors of random strings
• Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• Mean width of random perturbations of random polytopes
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• The work of Daniel A. Spielman
• Models of smoothing in dynamic networks
• A probabilistic PTAS for shortest common superstring
• On the smoothness of paging algorithms
• Smoothed analysis of condition numbers and complexity implications for linear programming
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Smoothed performance guarantees for local search
• In Praise of Numerical Computation
• The double pivot simplex method
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• Smoothed Analysis on Connected Graphs
• Robust smoothed analysis of a condition number for linear programming
• On realistic terrains
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• Smoothed analysis of balancing networks
• Why greed works for shortest common superstring problem
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• RANDOM MATRICES: THE CIRCULAR LAW
• A new look at the automatic synthesis of linear ranking functions
• Communication complexity of approximate Nash equilibria
• Mechanism design for policy routing
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• Diffusive influence systems
• Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean
• Relaxing the strong triadic closure problem for edge strength inference
• \(k\)-means requires exponentially many iterations even in the plane
• Smoothed analysis of binary search trees
• Learning with stochastic inputs and adversarial outputs
• On the shadow simplex method for curved polyhedra
• Implementing the simplex method as a cutting-plane method, with a view to regularization
• Book Review: The basic George B. Dantzig
• Smoothed analysis of complex conic condition numbers
• The probability that a slightly perturbed numerical analysis problem is difficult
• Smoothed analysis of integer programming
• Title not available (Why is that?)
• Smoothed analysis of dynamic networks
• A counterexample to the Hirsch conjecture
• Decision-making based on approximate and smoothed Pareto curves
• Recent development in computational complexity characterization of Nash equilibrium
• Computational complexity of kernel-based density-ratio estimation: a condition number analysis
• Approximating the minimum independent dominating set in perturbed graphs
• Smooth analysis of the condition number and the least singular value
• Cycles and matchings in randomly perturbed digraphs and hypergraphs

This page was built for publication: Smoothed analysis of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583576)