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)

Abstract

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 Creators	ORCiD
Panolan, Fahad	https://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