dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Simonov, Kirill | |
dc.date.accessioned | 2020-08-07T13:21:59Z | |
dc.date.available | 2020-08-07T13:21:59Z | |
dc.date.issued | 2019 | |
dc.Published | Fomin V, Golovach P, Simonov K. Parameterized k-Clustering: Tractability Island. Leibniz International Proceedings in Informatics. 2019;150:14:1-14:15 | eng |
dc.identifier.issn | 1868-8969 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/23581 | |
dc.description.abstract | In 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.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY | eng |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0 | eng |
dc.title | Parameterized k-Clustering: Tractability Island | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2020-01-17T14:50:36Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2019 The Author(s) | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.fsttcs.2019.14 | |
dc.identifier.cristin | 1774869 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.relation.project | Norges forskningsråd: 263317 | |