2026-07-21T14:14:06Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:12635 2024-03-06T10:51:19Z ddc:004 open_access
Low-Rank Binary Matrix Approximation in Column-Sum Norm Fomin, Fedor V. Golovach, Petr A. Panolan, Fahad Simonov, Kirill Binary Matrix Factorization PTAS Column-sum norm 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Fedor V. Fomin and Petr A. Golovach and Fahad Panolan and Kirill Simonov 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.32 urn:nbn:de:0030-drops-126355 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.32 eng https://creativecommons.org/licenses/by/3.0/legalcode