A quantization framework for smoothed analysis of Euclidean optimization problems (Q893320)

The maximum Euclidean matching, maximum Euclidean Traveling Salesman, the k-means clustering, and d-dimensional bin packing problems are considered. The proposed algorithms are based on the smoothed analysis where input instances are supposed chosen randomly with the worst case distribution density from a parametrised class of smooth densities. Average case complexity of the proposed algorithms is estimated, and it is shown that the approximation ratio converges to one with high probability. These algorithms can be adapted to yield asymptotically optimal expected approximation ratios.