Fomin, Fedor V and Golovach, Petr A and Panolan, Fahad
(2020)
Parameterized lowrank binary matrix approximation.
Data Mining and Knowledge Discovery.
ISSN 13845810
(In Press)
Full text not available from this repository.
(
Request a copy)
Abstract
Lowrank 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 NPhard. Due to this, we initiate the systematic algorithmic study of lowrank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixedparameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.
[error in script]
Actions (login required)

View Item 