| Geometric Clustering: Fixed-Parameter Tractability and Lower Bounds with Respect to the Dimension (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We present an algorithm for the 3-center problem in (R d, L∞), i. e., for finding the smallest side length for 3 cubes that cover a given n-point set in R d, that runs in O(n log n) time for any fixed dimension d. This shows that the problem is fixed-parameter tractable when parameterized with d. On the other hand, using tools from parameterized complexity theory, we show that this is unlikely to be the case with the k-center problem in (R d, L2), for any k ≥ 2. In particular, we prove that deciding whether a given n-point set in R d can be covered by the union of 2 balls of given radius is W[1]-hard with respect to d, and thus not fixed-parameter tractable unless FPT=W[1]. Our reduction also shows that even an O(n o(d))-time algorithm for the latter does not exist, unless SNP ⊂ DTIME(2 o(n)). Keywords: Clustering, Fixed-parameter tractability, Complexity, Lower bound, Dimension. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||