(UL)
  • Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension
    Cabello, Sergio ...
    We study the parameterized complexity of the ▫$k$▫-center problem on an given $n$-point set ▫$P$▫ in ▫${\mathbb{R}}^d$▫, with the dimension ▫$d$▫ as the parameter. We show that the rectilinear ... 3-center problem is fixed-parameter tractable, by giving an algorithm that runs in ▫$O(n \log n)$▫ time for any fixed dimension ▫$d$▫. On the other hand, we show that this is unlikely to be the case with both the Euclidean and rectilinear ▫$k$▫-center problems for any ▫$k\geq 2$▫ and ▫$k\geq 4$▫ respectively. In particular, we prove that deciding whether ▫$P$▫ can be covered by the union of ▫$2$▫ balls of given radius or by the union of 4 cubes of given side length is W[1]-hard with respect to ▫$d$▫, and thus not fixed-parameter tractable unless FPT=W[1]. For the Euclidean case we also show that even an ▫$n^{o(d)}$▫-time algorithm does not exist, unless there is a ▫$2^{o(n)}$▫-time algorithm for ▫$n$▫-variable 3SAT, i.e., the Exponential Time Hypothesis fails.
    Source: ACM transactions on algorithms. - ISSN 1549-6325 (Vol. 7, no. 4, 2011, Article 43 (27 str.))
    Type of material - article, component part
    Publish date - 2011
    Language - english
    COBISS.SI-ID - 16028761

    Link(s):

    http://dx.doi.org/10.1145/2000807.2000811

source: ACM transactions on algorithms. - ISSN 1549-6325 (Vol. 7, no. 4, 2011, Article 43 (27 str.))

loading ...
loading ...
loading ...

Shelf entry