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)- 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
- Mechanism design for perturbation stable combinatorial auctions
- A new look at the automatic synthesis of linear ranking functions
- The smoothed number of Pareto-optimal solutions in non-integer bicriteria optimization
- Mechanism design for policy routing
- Settling the complexity of local max-cut (almost) completely
- Rank aggregation: new bounds for MCx
- Adversarial meta-learning of Gamma-minimax estimators that leverage prior knowledge
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- Diffusive influence systems
- Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean
- Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
- Branch-and-bound solves random binary IPs in poly\((n)\)-time
- Fast Algorithms for Rank-1 Bimatrix Games
- A friendly smoothed analysis of the simplex method
- Relaxing the strong triadic closure problem for edge strength inference
- \(k\)-means requires exponentially many iterations even in the plane
- The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
- The square of a Hamilton cycle in randomly perturbed graphs
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Nonlinear biobjective optimization: improving the upper envelope using feasible line segments
- The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability
- Smoothed analysis for tensor methods in unsupervised learning
- Learning with stochastic inputs and adversarial outputs
- Smoothed analysis of binary search trees
- On the shadow simplex method for curved polyhedra
- Evaluating the quality of online optimization algorithms by discrete event simulation
- On the smoothed analysis of the smallest singular value with discrete noise
- Implementing the simplex method as a cutting-plane method, with a view to regularization
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Smoothed analysis of complex conic condition numbers
- Schur properties of randomly perturbed sets
- Smoothed analysis of integer programming
- Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits
- The probability that a slightly perturbed numerical analysis problem is difficult
- On the Condition Number of the Shifted Real Ginibre Ensemble
- Book Review: The basic George B. Dantzig
- Smoothed analysis of social choice revisited
- Analysis of FPTASes for the multi-objective shortest path problem
- A counterexample to the Hirsch conjecture
- Recent development in computational complexity characterization of Nash equilibrium
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- Decision-making based on approximate and smoothed Pareto curves
- The simultaneous semi-random model for TSP
- Bounds for the convergence time of local search in scheduling problems
- Approximating the minimum independent dominating set in perturbed graphs
- Cycles and matchings in randomly perturbed digraphs and hypergraphs
- Computational complexity of kernel-based density-ratio estimation: a condition number analysis
- Asymptotic density, immunity and randomness
- Smooth analysis of the condition number and the least singular value
- 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
- Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
- 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
- The Complexity of Diagonalization
- The conjugate gradient algorithm on a general class of spiked covariance matrices
- Algebraic Bayesian networks: checking backbone connectivity
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- On percolation and \(\mathcal{NP}\)-hardness
- Smoothed analysis. Motivation and discrete models
- 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)
