Smoothed analysis of partitioning algorithms for Euclidean functionals
From MaRDI portal
Publication:1950395
DOI10.1007/s00453-012-9643-5zbMath1279.90140MaRDI QIDQ1950395
Markus Bläser, Bodo Manthey, B. V. Raghavendra Rao
Publication date: 13 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9643-5
90C27: Combinatorial optimization
Related Items
Unnamed Item, Probabilistic properties of highly connected random geometric graphs, A quantization framework for smoothed analysis of Euclidean optimization problems, Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design, Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic, Smoothed Analysis of Local Search Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A partitioning algorithm for minimum weighted Euclidean matching
- Average-case approximation ratio of the 2-opt algorithm for the TSP
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- A proof of the Gilbert-Pollak conjecture on the Steiner ratio
- The Euclidean traveling salesman problem is NP-complete
- A matching problem and subadditive Euclidean functionals
- Probability theory of classical Euclidean optimization problems
- Extremal properties of sums of Bernoulli random variables.
- Smoothed analysis of left-to-right maxima with applications
- On two geometric problems related to the travelling salesman problem
- Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees
- Smoothed analysis of algorithms
- Complete Convergence of Short Paths and Karp's Algorithm for the TSP
- Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- The Complexity of Computing Steiner Minimal Trees
- Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in Rd
- Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
- On the weighted Euclidean matching problem in Rd
- Smoothed Analysis of Multiobjective Optimization
- Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
- Smoothed Analysis of the k-Means Method
- Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
- Probability and Computing
- Algorithms – ESA 2004
- The steiner problem in graphs
- Random knapsack in expected polynomial time
