Parameterized low-rank binary matrix approximation

Fomin, Fedor V and Golovach, Petr A and Panolan, Fahad (2020) Parameterized low-rank binary matrix approximation. Data Mining and Knowledge Discovery. ISSN 1384-5810 (In Press)

Full text not available from this repository. (Request a copy)

Abstract

Low-rank 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 NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, FahadUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Binary matrices, Clustering, Fixed-parameter tractability, Low-rank approximation, Indexed in Scopus and WoS
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 20 Jan 2020 05:55
Last Modified: 20 Jan 2020 05:55
URI: http://raiith.iith.ac.in/id/eprint/7357
Publisher URL: http://doi.org/10.1007/s10618-019-00669-5
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 7357 Statistics for this ePrint Item