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)- Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
- Column subset selection via sparse approximation of SVD
- The simultaneous semi-random model for TSP
- Relative Worst-Order Analysis: A Survey
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- Smoothed Analysis of Integer Programming
- From Parity and Payoff Games to Linear Programming
- Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
- A spectral approach to polytope diameter
- Quantum machine learning: a classical perspective
- Fast quantum subroutines for the simplex method
- The Synchronizing Probability Function for Primitive Sets of Matrices
- Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method
- Iterative computation of security strategies of matrix games with growing action set
- Smoothed analysis of probabilistic roadmaps
- On Smoothed Analysis of Quicksort and Hoare’s Find
- The effect of adding randomly weighted edges
- Counting environments and closures
- Bayesian incentive compatibility via matchings
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
- Performance guarantees for scheduling algorithms under perturbed machine speeds
- Asymptotic density and computability
- Smoothed analysis of the successive shortest path algorithm
- Quasi-decidability of a fragment of the first-order theory of real numbers
- The null space property for sparse recovery from multiple measurement vectors
- Smoothed analysis of the squared Euclidean maximum-cut problem
- Smoothed analysis of termination of linear programming algorithms
- Geometric random edge
- Smoothed analysis for the conjugate gradient algorithm
- PASS approximation: a framework for analyzing and designing heuristics
- The smoothed complexity of policy iteration for Markov decision processes
- Upper and lower bounds on the smoothed complexity of the simplex method
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Phase transition of degeneracy in minor-closed families
- Computing in combinatorial optimization
- The isotropic constant of random polytopes with vertices on convex surfaces
- A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
- Beyond the worst case: semi-random complexity analysis of winner determination
- scientific article; zbMATH DE number 7650102 (Why is no real title available?)
- Random perturbation of sparse graphs
- Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
- Counting frequent patterns in large labeled graphs: a hypergraph-based approach
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- On a condition number of general random polynomial systems
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- Approximating independent set in perturbed graphs
- Halting time is predictable for large models: a universality property and average-case analysis
- Learning a performance metric of Buchberger's algorithm
- Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- Smoothing the Gap Between NP and ER
- Mean width of random perturbations of random polytopes
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- Conditioning of random conic systems under a general family of input distributions
- George B. Dantzig and systems optimization
- George Dantzig's impact on the theory of computation
- Smoothed analysis of local search algorithms
- Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
- Running time of the treapsort algorithm
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- The smallest singular value of a shifted random matrix
- The work of Daniel A. Spielman
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Convex hulls of perturbed random point sets
- Mathematical Foundations of Computer Science 2003
- A probabilistic PTAS for shortest common superstring
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Nonparametric density estimation with nonuniform B-spline bases
- Speeding up random walk mixing by starting from a uniform vertex
- Complex random matrices have no real eigenvalues
- Models of smoothing in dynamic networks
- Smoothed performance guarantees for local search
- The double pivot simplex method
- Nearly optimal minimax estimator for high-dimensional sparse linear regression
- The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
- Stabilize deep ResNet with a sharp scaling factor \(\tau\)
- In Praise of Numerical Computation
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Moser's shadow problem
- Quantitative invertibility of random matrices: a combinatorial perspective
- Robust smoothed analysis of a condition number for linear programming
- On realistic terrains
- Smoothed Analysis on Connected Graphs
- A friendly smoothed analysis of the simplex method
- Circuits in extended formulations
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Optimizing MSE for clustering with balanced size constraints
- Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
- Why greed works for shortest common superstring problem
- Why Greed Works for Shortest Common Superstring Problem
- Approximation ineffectiveness of a tour-untangling heuristic
- On smoothed analysis of quicksort and Hoare's find
- On the enumeration of closures and environments with an application to random generation
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Internet routing between autonomous systems: fast algorithms for path trading
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- RANDOM MATRICES: THE CIRCULAR LAW
- Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
- Lower bounds for the smoothed number of Pareto optimal solutions
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)
