Fomin, Fedor V. ;
Golovach, Petr A. ;
Panolan, Fahad
Parameterized LowRank Binary Matrix Approximation
Abstract
We provide a number of algorithmic results for the following family of problems: For a given binary m x n matrix A and a nonnegative integer k, decide whether there is a "simple" binary matrix B which differs from A in at most k entries. For an integer r, the "simplicity" of B is characterized as follows.
 Binary rMeans: Matrix B has at most r different columns. This problem is known to be NPcomplete already for r=2. We show that the problem is solvable in time 2^{O(k log k)}*(nm)^O(1) and thus is fixedparameter tractable parameterized by k. We also complement this result by showing that when being parameterized by r and k, the problem admits an algorithm of running time 2^{O(r^{3/2}* sqrt{k log k})}(nm)^O(1), which is subexponential in k for r in o((k/log k)^{1/3}).
 Low GF(2)Rank Approximation: Matrix B is of GF(2)rank at most r. This problem is known to be NPcomplete already for r=1. It is also known to be W[1]hard when parameterized by k. Interestingly, when parameterized by r and k, the problem is not only fixedparameter tractable, but it is solvable in time 2^{O(r^{3/2}* sqrt{k log k})}(nm)^O(1), which is subexponential in k for r in o((k/log k)^{1/3}).
 Low BooleanRank Approximation: Matrix B is of Boolean rank at most r. The problem is known to be NPcomplete for k=0 as well as for r=1. We show that it is solvable in subexponential in k time 2^{O(r2^r * sqrt{k log k})}(nm)^O(1).
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2018:9057,
author = {Fedor V. Fomin and Petr A. Golovach and Fahad Panolan},
title = {{Parameterized LowRank Binary Matrix Approximation}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {53:153:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9057},
URN = {urn:nbn:de:0030drops90571},
doi = {10.4230/LIPIcs.ICALP.2018.53},
annote = {Keywords: Binary matrices, clustering, lowrank approximation, fixedparameter tractability}
}
04.07.2018
Keywords: 

Binary matrices, clustering, lowrank approximation, fixedparameter tractability 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 