When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.53
URN: urn:nbn:de:0030-drops-90571
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9057/
 Go to the corresponding LIPIcs Volume Portal

Parameterized Low-Rank Binary Matrix Approximation

 pdf-format:

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 r-Means: Matrix B has at most r different columns. This problem is known to be NP-complete already for r=2. We show that the problem is solvable in time 2^{O(k log k)}*(nm)^O(1) and thus is fixed-parameter 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 NP-complete 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 fixed-parameter 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 Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The problem is known to be NP-complete 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 Low-Rank Binary Matrix Approximation}},
booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
pages =	{53:1--53:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-076-7},
ISSN =	{1868-8969},
year =	{2018},
volume =	{107},
editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},