Smoothed analysis of algorithms

DOI10.1145/990308.990310zbMATH Open1192.90120DBLPjournals/jacm/SpielmanT04OpenAlexW2034053794WikidataQ55952478 ScholiaQ55952478MaRDI QIDQ3583576FDOQ3583576

Authors: Daniel A. Spielman, Shang-Hua Teng 

Publication date: 17 August 2010

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/990308.990310

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

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (only showing first 100 items - show all)

• Complex random matrices have no real eigenvalues
• Stabilize deep ResNet with a sharp scaling factor \(\tau\)
• Moser's shadow problem
• Quantitative invertibility of random matrices: a combinatorial perspective
• Optimizing MSE for clustering with balanced size constraints
• Why Greed Works for Shortest Common Superstring Problem
• On smoothed analysis of quicksort and Hoare's find
• Internet routing between autonomous systems: fast algorithms for path trading
• Mechanism design for perturbation stable combinatorial auctions
• A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities
• Rank aggregation: new bounds for MCx
• The Effect of Adding Randomly Weighted Edges
• 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 the smoothed analysis of the smallest singular value with discrete noise
• 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
• On the Condition Number of the Shifted Real Ginibre Ensemble
• Analysis of FPTASes for the multi-objective shortest path problem
• Asymptotic density, immunity and randomness
• 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
• The conjugate gradient algorithm on a general class of spiked covariance matrices
• Algebraic Bayesian networks: checking backbone connectivity
• Relative Worst-Order Analysis: A Survey
• The simultaneous semi-random model for TSP
• Smoothed Analysis of Integer Programming
• Quantum machine learning: a classical perspective
• Fast quantum subroutines for the simplex method
• On Smoothed Analysis of Quicksort and Hoare’s Find
• Iterative computation of security strategies of matrix games with growing action set
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
• Smoothed analysis of the successive shortest path algorithm
• Asymptotic density and computability
• Bounds for the Convergence Time of Local Search in Scheduling Problems
• PASS approximation: a framework for analyzing and designing heuristics
• Computing in combinatorial optimization
• Beyond the worst case: semi-random complexity analysis of winner determination
• Title not available (Why is that?)
• A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
• Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm
• Random perturbation of sparse graphs
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Improved smoothed analysis of multiobjective optimization
• Counting frequent patterns in large labeled graphs: a hypergraph-based approach
• Smoothed complexity theory
• Maximal unbordered factors of random strings
• Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
• Mean width of random perturbations of random polytopes
• On the efficiency of a randomized mirror descent algorithm in online optimization problems
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• The work of Daniel A. Spielman
• Models of smoothing in dynamic networks
• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
• A Friendly Smoothed Analysis of the Simplex Method
• Circuits in extended formulations
• Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
• On percolation and ‐hardness
• Approximation ineffectiveness of a tour-untangling heuristic
• On the enumeration of closures and environments with an application to random generation
• Lower bounds for the smoothed number of Pareto optimal solutions
• Adversarial meta-learning of Gamma-minimax estimators that leverage prior knowledge
• Settling the complexity of local max-cut (almost) completely
• Branch-and-bound solves random binary IPs in poly\((n)\)-time
• Fast Algorithms for Rank-1 Bimatrix Games
• The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
• The square of a Hamilton cycle in randomly perturbed graphs
• The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability
• Title not available (Why is that?)
• Schur properties of randomly perturbed sets
• Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits
• Smoothed analysis of social choice revisited
• The simultaneous semi-random model for TSP
• 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
• The Complexity of Diagonalization
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• A spectral approach to polytope diameter
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Smoothed analysis of the squared Euclidean maximum-cut problem
• Smoothed analysis for the conjugate gradient 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
• Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Learning a performance metric of Buchberger's algorithm
• 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
• Halting time is predictable for large models: a universality property and average-case analysis
• Smoothing the Gap Between NP and ER
• Smoothed analysis of local search algorithms
• Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
• Nonparametric density estimation with nonuniform B-spline bases
• Speeding up random walk mixing by starting from a uniform vertex
• A probabilistic PTAS for shortest common superstring
• On the smoothness of paging algorithms
• Smoothed analysis of condition numbers and complexity implications for linear programming

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)