文章基本信息

标题：Low-Rank Binary Matrix Approximation in Column-Sum Norm
本地全文：下载
作者：Fedor V. Fomin ; Petr A. Golovach ; Fahad Panolan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：32:1-32:18
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider ð"â,-Rank-r Approximation over {GF}(2), where for a binary mÃ- n matrix ð and a positive integer constant r, one seeks a binary matrix ð of rank at most r, minimizing the column-sum norm â- ð -ðâ-â,. We show that for every Îµ â^^ (0, 1), there is a {randomized} (1+Îµ)-approximation algorithm for ð"â,-Rank-r Approximation over {GF}(2) of running time m^{O(1)}n^{O(2^{4r}â<. Îµ^{-4})}. This is the first polynomial time approximation scheme (PTAS) for this problem.
关键词：Binary Matrix Factorization; PTAS; Column-sum norm