2026-07-23T10:34:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11576 2024-03-06T10:48:21Z ddc:004 open_access

Parameterized k-Clustering: Tractability Island Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill clustering parameterized complexity k-means k-median 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Kirill Simonov 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.14 urn:nbn:de:0030-drops-115761 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.14 eng https://creativecommons.org/licenses/by/3.0/legalcode