Smoothed analysis of partitioning algorithms for Euclidean functionals
type: Item
instance of: scholarly article
title: Smoothed analysis of partitioning algorithms for Euclidean functionals
zbMATH Open document ID: 1279.90140
author: Markus Bläser
author: Bodo Manthey
author: B. V. Raghavendra Rao
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
review text: In Euclidean optimization problems we consider a set \(X\) of points in \(\mathbb{R}^2\) with Euclidean distance \(\|x-y\|\). Some of them are NP-hard (e.g. the Euclidean TSP or Euclidean Steiner tree problem). For others (e.g. minimum length perfect matching) there exist polynomial-time algorithms which are sometimes too slow to solve large instances. This paper focuses on fast partitioning algorithms as heuristics that compute near-optimal solutions on typical instances: divide the Euclidean plane into a number of cells s.t. each cell contains only a small number of points, quickly compute the optimum solution within each cell and, finally, join the solutions of all cells into an approximate solution for \(X\). In order to analyse and prove the performance of a heuristic, the authors develop a general framework for the application of smoothed analysis to partitioning algorithms for Euclidean optimization problems. It can be used to analyze both the running-time and the approximation ratio of such algorithms. They consider \(n=|X|\) density functions \(f_1,\dots,f_n:[0,1]^2\rightarrow[0,\phi]\): \(f_i\) used to move a point \(x_i\) independently from the others. Expected running time and approximation performance of Dyer and Frieze's partitioning algorithm for the Euclidean matching, Karp's partitioning scheme for the TSP, a heuristic for Steiner trees, and a heuristic for degree-bounded minimum-length spanning trees are analysed under this model.
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6162397
zbMATH Keywords: partitioning algorithms
zbMATH Keywords: Euclidean optimization problems
zbMATH Keywords: smoothed analysis
MaRDI profile type: Publication
full work available at URL: s00453-012-9643-5
OpenAlex ID: W2493827104
cites work: Q3056948
cites work: On the weighted Euclidean matching problem in Rd
cites work: Smoothed Analysis of the k-Means Method
cites work: Random knapsack in expected polynomial time
cites work: Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
cites work: Smoothed analysis of left-to-right maxima with applications
cites work: Algorithms – ESA 2004
cites work: The steiner problem in graphs
cites work: A proof of the Gilbert-Pollak conjecture on the Steiner ratio
cites work: A partitioning algorithm for minimum weighted Euclidean matching
cites work: Average-case approximation ratio of the 2-opt algorithm for the TSP
cites work: Q2934725
cites work: Q4461909
cites work: The Complexity of Computing Steiner Minimal Trees
cites work: Q4875192
cites work: Q4461911
cites work: Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in Rd
cites work: Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
cites work: Extremal properties of sums of Bernoulli random variables.
cites work: Probability and Computing
cites work: The Euclidean traveling salesman problem is NP-complete
cites work: On two geometric problems related to the travelling salesman problem
cites work: Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
cites work: A matching problem and subadditive Euclidean functionals
cites work: Smoothed Analysis of Multiobjective Optimization
cites work: Smoothed analysis of algorithms
cites work: Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
cites work: Complete Convergence of Short Paths and Karp's Algorithm for the TSP
cites work: Subadditive Euclidean functionals and nonlinear growth in geometric probability
cites work: Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees
cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
cites work: Probability theory of classical Euclidean optimization problems
DOI: 10.1007/S00453-012-9643-5
description: scientific article; zbMATH DE number 6162397