Low-rank binary matrix approximation in column-sum norm

Fomin, F.V. and Golovach, P.A. and Panolan, Fahad and Simonov, K. (2020) Low-rank binary matrix approximation in column-sum norm. In: 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020, 17-19 August 2020, Virtual, Online.

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


We consider ℓ1-Rank-r Approximation over GF(2), where for a binary m × n matrix A and a positive integer constant r, one seeks a binary matrix B of rank at most r, minimizing the column-sum norm ||A − B||1. We show that for every ε ∈ (0, 1), there is a randomized (1 + ε)-approximation algorithm for ℓ1-Rank-r Approximation over GF(2) of running time mO(1)nO(24r·ε−4). This is the first polynomial time approximation scheme (PTAS) for this problem. © 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Conference or Workshop Item (Paper)
Additional Information: Funding Fedor V. Fomin: The research leading to these results have been supported by the Research Council of Norway via the project “MULTIVAL” (grant 263317). The work was done within the CEDAS center in Bergen.
Uncontrolled Keywords: Binary Matrix Factorization, Column-sum norm, PTAS
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 23 Nov 2022 09:34
Last Modified: 23 Nov 2022 09:34
URI: http://raiith.iith.ac.in/id/eprint/11226
Publisher URL: https://10.4230/LIPIcs.APPROX/RANDOM.2020.32
OA policy: https://v2.sherpa.ac.uk/id/publication/29495
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 11226 Statistics for this ePrint Item