Parameterized low-rank binary matrix approximation

Fomin, Fedor V and Golovach, Petr A and Panolan, Fahad (2020) Parameterized low-rank binary matrix approximation. Data Mining and Knowledge Discovery. ISSN 1384-5810 (In Press)

Full text not available from this repository. (Request a copy)

Abstract

Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference between the two matrices in some matrix norm is small. The properties of the approximation binary matrix could be: a small number of different columns, a small binary rank or a small Boolean rank. Unfortunately, most variants of these problems are NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.

[error in script]

IITH Creators: