Smoothed Analysis of Local Search Algorithms
From MaRDI portal
Publication:3449848
DOI10.1007/978-3-319-21840-3_43zbMath1451.68360MaRDI QIDQ3449848
Publication date: 30 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21840-3_43
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smoothed performance guarantees for local search
- Performance guarantees for scheduling algorithms under perturbed machine speeds
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Smoothed analysis of complex conic condition numbers
- Smoothed analysis of integer programming
- Smoothed analysis of probabilistic roadmaps
- Smoothed analysis of termination of linear programming algorithms
- Modeling language evolution
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Internet routing between autonomous systems: fast algorithms for path trading
- Smoothed analysis of binary search trees
- 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
- Topology matters: smoothed competitiveness of metrical task systems
- A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems
- Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
- Visibility maps of realistic terrains have linear smoothed complexity
- Worst-case and smoothed analysis of k-means clustering with Bregman divergences
- Settling the Complexity of Local Max-Cut (Almost) Completely
- Smooth analysis of the condition number and the least singular value
- Smoothed analysis of left-to-right maxima with applications
- The smoothed complexity of edit distance
- Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
- On smoothed analysis in dense graphs and formulas
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- Settling the complexity of computing two-player Nash equilibria
- Smoothed Analysis of the Successive Shortest Path Algorithm
- Equilibria with Communication in a Job Market Example
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- The probability that a slightly perturbed numerical analysis problem is difficult
- Smoothed analysis of algorithms
- New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
- Pareto Optimal Solutions for Smoothed Analysts
- Learning and Smoothed Analysis
- Smoothed Analysis of Multiobjective Optimization
- Smoothed analysis of balancing networks
- The diameter of randomly perturbed digraphs and some applications
- Smoothed Analysis of Local Search for the Maximum-Cut Problem
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Smoothed Analysis of the k-Means Method
- Improved smoothed analysis of multiobjective optimization
- The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
- Mathematical Foundations of Computer Science 2003
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Smoothed Complexity Theory
- Random knapsack in expected polynomial time
