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

"Parameterized Complexity Results for the Completion and Clustering of Incomplete Data";

Talk: Kocoon Workshop, Arras, Frankreich; 2019-12-16 - 2019-12-19.

We consider the following data completion problem: Given an incomplete matrix and a set of constraints, the goal is to complete the matrix such that

each row satisfies the input constraints and

the complete matrix can be clustered into few subspaces with low rank.

This problem generalizes several problems in data mining and machine learning, and is related to ranking problems over incomplete data studied in the context knowledge compilation by Choi et al. We draw a detailed complexity landscape with respect to natural parameters and well-studied CSP fragments. Joint work with Robert Ganian, Iyad Kanj, and Sebastian Ordyniak.

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