Smoothed analysis of algorithms
From MaRDI portal
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)- Smoothed analysis of probabilistic roadmaps
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Conditioning of random conic systems under a general family of input distributions
- Why greed works for shortest common superstring problem
- Smoothed analysis of termination of linear programming algorithms
- Rank aggregation: new bounds for MCx
- Evaluating the quality of online optimization algorithms by discrete event simulation
- Analysis of FPTASes for the multi-objective shortest path problem
- Mean width of random perturbations of random polytopes
- Research on the efficient computation mechanism -- in the case of N-vehicle exploration problem
- Computational complexity of kernel-based density-ratio estimation: a condition number analysis
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- PASS approximation: a framework for analyzing and designing heuristics
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Relaxing the strong triadic closure problem for edge strength inference
- Quasi-decidability of a fragment of the first-order theory of real numbers
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Nonlinear biobjective optimization: improving the upper envelope using feasible line segments
- Random perturbation of sparse graphs
- Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Gaining traction: on the convergence of an inner approximation scheme for probability maximization
- Algebraic Bayesian networks: checking backbone connectivity
- Fast quantum subroutines for the simplex method
- Asymptotic density and computability
- Computing in combinatorial optimization
- Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- Stabilize deep ResNet with a sharp scaling factor \(\tau\)
- Smoothed analysis for tensor methods in unsupervised learning
- The simultaneous semi-random model for TSP
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Counting frequent patterns in large labeled graphs: a hypergraph-based approach
- Convex hulls of perturbed random point sets
- The isotropic constant of random polytopes with vertices on convex surfaces
- Iterative computation of security strategies of matrix games with growing action set
- Moser's shadow problem
- Optimizing MSE for clustering with balanced size constraints
- Internet routing between autonomous systems: fast algorithms for path trading
- On the efficiency of a randomized mirror descent algorithm in online optimization problems
- Geometric random edge
- Decision-making based on approximate and smoothed Pareto curves
- Smoothed analysis of binary search trees
- Mechanism design for policy routing
- Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
- Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
- On smoothed analysis of quicksort and Hoare's find
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Approximating independent set in perturbed graphs
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Bayesian incentive compatibility via matchings
- Smoothed analysis for the conjugate gradient algorithm
- Topology matters: smoothed competitiveness of metrical task systems
- Phase transition of degeneracy in minor-closed families
- Halting time is predictable for large models: a universality property and average-case analysis
- On a condition number of general random polynomial systems
- Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean
- Smoothed Analysis on Connected Graphs
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Bounds for the convergence time of local search in scheduling problems
- On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
- The smoothed number of Pareto-optimal solutions in non-integer bicriteria optimization
- Lower bounds for the smoothed number of Pareto optimal solutions
- Stochastic mean payoff games: smoothed analysis and approximation schemes
- Settling the complexity of local max-cut (almost) completely
- The work of Daniel A. Spielman
- Smooth analysis of the condition number and the least singular value
- From Parity and Payoff Games to Linear Programming
- Asymptotic density, immunity and randomness
- Smoothed analysis of the minimum-mean cycle canceling algorithm and the network simplex algorithm
- Cycles and matchings in randomly perturbed digraphs and hypergraphs
- A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
- Quantitative invertibility of random matrices: a combinatorial perspective
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- Diffusive influence systems
- Smoothed analysis of local search algorithms
- Smoothed analysis of the squared Euclidean maximum-cut problem
- Smoothed analysis of the successive shortest path algorithm
- A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
- Why Greed Works for Shortest Common Superstring Problem
- RANDOM MATRICES: THE CIRCULAR LAW
- The probability that a slightly perturbed numerical analysis problem is difficult
- Smoothed Analysis of Integer Programming
- Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
- In Praise of Numerical Computation
- Implementing the simplex method as a cutting-plane method, with a view to regularization
- Nearly optimal minimax estimator for high-dimensional sparse linear regression
- Running time of the treapsort algorithm
- A probabilistic PTAS for shortest common superstring
- Smoothed performance guarantees for local search
- Learning with stochastic inputs and adversarial outputs
- A counterexample to the Hirsch conjecture
- Quantum machine learning: a classical perspective
- Recent development in computational complexity characterization of Nash equilibrium
- Complex random matrices have no real eigenvalues
- On percolation and \(\mathcal{NP}\)-hardness
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- Performance guarantees for scheduling algorithms under perturbed machine speeds
- On the enumeration of closures and environments with an application to random generation
- The effect of adding randomly weighted edges
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)
