R. Ganian, I. Kanj, S. Ordyniak,S. Szeider:

"On the Parameterized Complexity ofClustering Incomplete Data into Subspaces of Small Dimension";

Talk: AAAI 2020, New York, USA; 2020-02-07 - 2020-02-12; in: "Proceedings of AAAI2020", AAAI Press, 34 (2020), ISSN: 2374-3468; 3906 - 3913.

We consider a fundamental matrix completion problem wherewe are given an incomplete matrix and a set of constraintsmodeled as a CSP instance. The goal is to complete the matrixsubject to the input constraints, and in such a way that thecomplete matrix can be clustered into few subspaces withlow dimension. This problem generalizes several problems indata mining and machine learning, including the problem ofcompleting a matrix into one with minimum rank. In additionto its ubiquitous applications in machine learning, the problemhas strong connections to information theory, related to binarylinear codes, and variants of it have been extensively studiedfrom that perspective.We formalize the problem mentioned above and study its clas-sical and parameterized complexity with respect to severalnatural parameters that are desirably small, and with respect tothe CSP fragment from which the set of constraints is drawn.We draw a detailed landscape of the complexity and parameter-ized complexity of the problem with respect to the parametersunder consideration, and with respect to several well-studiedCSP fragments.

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

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