Fomin, Fedor V and Golovach, Petr A and Panolan, Fahad and et al, .
(2019)
Approximation Schemes for Lowrank Binary Matrix Approximation Problems.
ACM Transactions on Algorithms, 16 (1).
pp. 139.
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 timeapproximation schemes for a number of wellstudied fundamental problems concerning clustering of binary vectors and lowrank approximation of binary matrices. Among the problems solvable by our approach are Low GF(2)Rank Approximation, Low BooleanRank 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 ∂0norm 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]
Actions (login required)

View Item 