Smoothed analysis of algorithms
From MaRDI portal
Publication:3583576
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
Cited in
(only showing first 100 items - show all)- Fast quantum subroutines for the simplex method
- Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
- Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
- The conjugate gradient algorithm on a general class of spiked covariance matrices
- On the smoothed analysis of the smallest singular value with discrete noise
- 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
- On the Condition Number of the Shifted Real Ginibre Ensemble
- Moser's shadow problem
- Complex random matrices have no real eigenvalues
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- Quantum machine learning: a classical perspective
- Rank aggregation: new bounds for MCx
- Asymptotic density, immunity and randomness
- Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- On smoothed analysis of quicksort and Hoare's find
- Beyond the worst case: semi-random complexity analysis of winner determination
- Counting frequent patterns in large labeled graphs: a hypergraph-based approach
- Quantitative invertibility of random matrices: a combinatorial perspective
- Analysis of FPTASes for the multi-objective shortest path problem
- scientific article; zbMATH DE number 7650102 (Why is no real title available?)
- Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
- Mechanism design for perturbation stable combinatorial auctions
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- Why Greed Works for Shortest Common Superstring Problem
- 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 Smoothed Analysis of Quicksort and Hoare’s Find
- Iterative computation of security strategies of matrix games with growing action set
- Random perturbation of sparse graphs
- PASS approximation: a framework for analyzing and designing heuristics
- Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
- Relative Worst-Order Analysis: A Survey
- Mean width of random perturbations of random polytopes
- Internet routing between autonomous systems: fast algorithms for path trading
- Computing in combinatorial optimization
- Stabilize deep ResNet with a sharp scaling factor \(\tau\)
- Smoothed Analysis of Integer Programming
- Asymptotic density and computability
- The effect of adding randomly weighted edges
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- The work of Daniel A. Spielman
- Optimizing MSE for clustering with balanced size constraints
- Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem
- A friendly smoothed analysis of the simplex method
- 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
- Bounds for the convergence time of local search in scheduling problems
- The simultaneous semi-random model for TSP
- Algebraic Bayesian networks: checking backbone connectivity
- Models of smoothing in dynamic networks
- Quasi-decidability of a fragment of the first-order theory of real numbers
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Smoothed Analysis on Connected Graphs
- \(k\)-means requires exponentially many iterations even in the plane
- Cycles and matchings in randomly perturbed digraphs and hypergraphs
- Performance guarantees for scheduling algorithms under perturbed machine speeds
- RANDOM MATRICES: THE CIRCULAR LAW
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Learning with stochastic inputs and adversarial outputs
- A probabilistic PTAS for shortest common superstring
- Book Review: The basic George B. Dantzig
- Smoothed analysis of complex conic condition numbers
- Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean
- Implementing the simplex method as a cutting-plane method, with a view to regularization
- Conditioning of random conic systems under a general family of input distributions
- The probability that a slightly perturbed numerical analysis problem is difficult
- Smoothed analysis of condition numbers and complexity implications for linear programming
- The isotropic constant of random polytopes with vertices on convex surfaces
- Column subset selection via sparse approximation of SVD
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- Bayesian incentive compatibility via matchings
- Geometric random edge
- Robust smoothed analysis of a condition number for linear programming
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- On realistic terrains
- George B. Dantzig and systems optimization
- George Dantzig's impact on the theory of computation
- Smoothed analysis of termination of linear programming algorithms
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Smoothed analysis of integer programming
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- On a condition number of general random polynomial systems
- Diffusive influence systems
- Smoothed performance guarantees for local search
- The null space property for sparse recovery from multiple measurement vectors
- Computational complexity of kernel-based density-ratio estimation: a condition number analysis
- Approximating the minimum independent dominating set in perturbed graphs
- In Praise of Numerical Computation
- The double pivot simplex method
- A quantization framework for smoothed analysis of Euclidean optimization problems
- Convex hulls of perturbed random point sets
- Smoothed heights of tries and patricia tries
- Smooth analysis of the condition number and the least singular value
- Nearly optimal minimax estimator for high-dimensional sparse linear regression
- Why greed works for shortest common superstring problem
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)
