Smoothed analysis of partitioning algorithms for Euclidean functionals

DOI10.1007/s00453-012-9643-5zbMath1279.90140OpenAlexW2493827104MaRDI 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

zbMATH Keywords

smoothed analysispartitioning algorithmsEuclidean optimization problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (6)

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Unnamed Item ⋮ Probabilistic properties of highly connected random geometric graphs

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 R^d
• Experimental evaluation of a partitioning algorithm for the steiner tree problem in R² and R³
• On the weighted Euclidean matching problem in R^d
• 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

This page was built for publication: Smoothed analysis of partitioning algorithms for Euclidean functionals