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

Created from the Publication Database of the Vienna University of Technology.