Smoothed analysis of partitioning algorithms for Euclidean functionals (Q1950395)

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.