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


Fomin, Fedor V. ; Golovach, Petr A. ; Panolan, Fahad

Parameterized Low-Rank Binary Matrix Approximation

pdf-format:
LIPIcs-ICALP-2018-53.pdf (0.6 MB)


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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9057},
  URN =		{urn:nbn:de:0030-drops-90571},
  doi =		{10.4230/LIPIcs.ICALP.2018.53},
  annote =	{Keywords: Binary matrices, clustering, low-rank approximation, fixed-parameter tractability}
}

Keywords: Binary matrices, clustering, low-rank approximation, fixed-parameter tractability
Seminar: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 29.06.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI