Approximation Schemes for Low-rank Binary Matrix Approximation Problems

Fomin, Fedor V and Golovach, Petr A and Panolan, Fahad and et al, . (2019) Approximation Schemes for Low-rank Binary Matrix Approximation Problems. ACM Transactions on Algorithms, 16 (1). pp. 1-39. ISSN 15496325

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

Abstract

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constraints. The new constrained clustering problem generalizes a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are Low GF(2)-Rank Approximation, Low Boolean-Rank Approximation, and various versions of Binary Clustering. For example, for Low GF(2)- Rank Approximation problem, where for anm × n binary matrix A and integer r > 0, we seek for a binary matrix B of GF(2) rank at most r such that the ∂0-norm of matrix A - B is minimum, our algorithm, for any ∈ > 0 in time f (r , ∈ ) nm, where f is some computable function, outputs a (1 + ∈ )-approximate solution with probability at least (1 - 1 e ). This is the first linear time approximation scheme for these problems. We also give (deterministic) PTASes for these problems running in time nf (r ) 1 ∈2 log 1 ∈ , where f is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting on its own.

[error in script]

IITH Creators: