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
- Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- A friendly smoothed analysis of the simplex method
- The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
- Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
- On percolation and \(\mathcal{NP}\)-hardness
- The square of a Hamilton cycle in randomly perturbed graphs
- Smoothed analysis of social choice revisited
- On the enumeration of closures and environments with an application to random generation
- Branch-and-bound solves random binary IPs in poly\((n)\)-time
- Schur properties of randomly perturbed sets
- The simultaneous semi-random model for TSP
- Smoothed analysis for the conjugate gradient algorithm
- Learning a performance metric of Buchberger's algorithm
- The smoothed complexity of policy iteration for Markov decision processes
- Upper and lower bounds on the smoothed complexity of the simplex method
- Phase transition of degeneracy in minor-closed families
- 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
- The smoothed number of Pareto-optimal solutions in non-integer bicriteria optimization
- Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
- Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
- Approximation ineffectiveness of a tour-untangling heuristic
- Adversarial meta-learning of Gamma-minimax estimators that leverage prior knowledge
- Lower bounds for the smoothed number of Pareto optimal solutions
- The Synchronizing Probability Function for Primitive Sets of Matrices
- The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability
- The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
- A spectral approach to polytope diameter
- Halting time is predictable for large models: a universality property and average-case analysis
- The Complexity of Diagonalization
- Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits
- Settling the complexity of local max-cut (almost) completely
- Circuits in extended formulations
- Smoothed analysis of local search algorithms
- Nonparametric density estimation with nonuniform B-spline bases
- Counting environments and closures
- Smoothing the Gap Between NP and ER
- Speeding up random walk mixing by starting from a uniform vertex
- Smoothed analysis of the squared Euclidean maximum-cut problem
- Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
- Fast Algorithms for Rank-1 Bimatrix Games
- 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
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)
