Smoothed analysis of algorithms
From MaRDI portal
Publication:3583576
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
Linear programming (90C05) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (only showing first 100 items - show all)
- 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
- Topology matters: smoothed competitiveness of metrical task systems
- On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
- A quantization framework for smoothed analysis of Euclidean optimization problems
- Smoothed heights of tries and patricia tries
- Smoothed analysis. Motivation and discrete models
- Cycles and matchings in randomly perturbed digraphs and hypergraphs
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Column subset selection via sparse approximation of SVD
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- From Parity and Payoff Games to Linear Programming
- Smoothed analysis of probabilistic roadmaps
- Bayesian incentive compatibility via matchings
- Quasi-decidability of a fragment of the first-order theory of real numbers
- Performance guarantees for scheduling algorithms under perturbed machine speeds
- Geometric random edge
- Smoothed analysis of termination of linear programming algorithms
- The null space property for sparse recovery from multiple measurement vectors
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- The isotropic constant of random polytopes with vertices on convex surfaces
- On a condition number of general random polynomial systems
- Approximating independent set in perturbed graphs
- The smallest singular value of a shifted random matrix
- Conditioning of random conic systems under a general family of input distributions
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- George B. Dantzig and systems optimization
- George Dantzig's impact on the theory of computation
- Running time of the treapsort algorithm
- Mathematical Foundations of Computer Science 2003
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Convex hulls of perturbed random point sets
- 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
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)
