2026-07-26T01:27:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9057 2024-03-06T10:43:15Z ddc:004 open_access

Parameterized Low-Rank Binary Matrix Approximation Fomin, Fedor V. Golovach, Petr A. Panolan, Fahad Binary matrices clustering low-rank approximation fixed-parameter tractability 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Fahad Panolan 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.53 urn:nbn:de:0030-drops-90571 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.53 eng https://creativecommons.org/licenses/by/3.0/legalcode