A quantization framework for smoothed analysis of Euclidean optimization problems (Q893320)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A quantization framework for smoothed analysis of Euclidean optimization problems |
scientific article |
Statements
A quantization framework for smoothed analysis of Euclidean optimization problems (English)
0 references
19 November 2015
0 references
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.
0 references
average case complexity
0 references
smoothed analysis
0 references
Euclidean optimization problems
0 references
bin packing
0 references
maximum matching
0 references
travelling salesman
0 references
0 references
0 references
0 references