Smoothed Analysis of Local Search Algorithms

DOI10.1007/978-3-319-21840-3_43zbMath1451.68360OpenAlexW1602567940MaRDI QIDQ3449848

Bodo Manthey

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

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

This page was built for publication: Smoothed Analysis of Local Search Algorithms