Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorSimonov, Kirill
dc.PublishedFomin V, Golovach P, Simonov K. Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 2019;150:14:1-14:15eng
dc.description.abstractIn k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} sum_{x in C_i} |x-c_i|_p^p <= D, where |*|_p is the Minkowski (L_p) norm of order p. For p=1, k-Clustering is the well-known k-Median. For p=2, the case of the Euclidean distance, k-Clustering is k-Means. We study k-Clustering from the perspective of parameterized complexity. The problem is known to be NP-hard for k=2 and it is also NP-hard for d=2. It is a long-standing open question, whether the problem is fixed-parameter tractable (FPT) for the combined parameter d+k. In this paper, we focus on the parameterization by D. We complement the known negative results by showing that for p=0 and p=infty, k-Clustering is W1-hard when parameterized by D. Interestingly, the complexity landscape of the problem appears to be more intricate than expected. We discover a tractability island of k-Clustering: for every p in (0,1], k-Clustering is solvable in time 2^O(D log D) (nd)^O(1).en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BYeng
dc.titleParameterized k-Clustering: Tractability Islanden_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2019 The Author(s)en_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.relation.projectNorges forskningsråd: 263317

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY
Except where otherwise noted, this item's license is described as Attribution CC BY