[Back]

E. Eiben, R. Ganian, I. Kanj, S. Ordyniak, S. Szeider:
"The Parameterized Complexity of Clustering Incomplete Data";
Talk: 35th AAAI 2021, virtual event; 2021-02-02 - 2021-02-09; in: "Thirty-Fifth AAAI Conference on Artificial Intelligence", AAAI Press, 35 (2021), ISBN: 978-1-57735-866-4; 7296 - 7304.

We study fundamental clustering problems for incomplete
data. Specifically, given a set of incomplete d-dimensional
vectors (representing rows of a matrix), the goal is to complete
the missing vector entries in a way that admits a partitioning
of the vectors into at most k clusters with radius
or diameter at most r. We give tight characterizations of the
parameterized complexity of these problems with respect to
the parameters k, r, and the minimum number of rows and
columns needed to cover all the missing entries. We show
that the considered problems are fixed-parameter tractable
when parameterized by the three parameters combined, and
that dropping any of the three parameters results in parameterized
intractability. A byproduct of our results is that, for
the complete data setting, all problems under consideration
are fixed-parameter tractable parameterized by k + r.

https://publik.tuwien.ac.at/files/publik_300056.pdf