Probabilistic analysis of some euclidean clustering problems |
| |
Authors: | AM Frieze |
| |
Institution: | Dept. of Computer Science and Statistics, Queen Mary College, Mile End Road, London, E1 4NS, England |
| |
Abstract: | We are given n points distributed randomly in a compact region D of Rm. We consider various optimisation problems associated with partitioning this set of points into k subsets. For each problem we demonstrate lower bounds which are satisfied with high probability. For the case where D is a hypercube we use a partitioning technique to give deterministic upper bounds and to construct algorithms which with high probability can be made arbitrarily accurate in polynomial time for a given required accuracy. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|