dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Panolan, Fahad | |
dc.contributor.author | Simonov, Kirill | |
dc.date.accessioned | 2021-05-19T12:54:27Z | |
dc.date.available | 2021-05-19T12:54:27Z | |
dc.date.created | 2021-01-04T12:44:21Z | |
dc.date.issued | 2020 | |
dc.Published | Leibniz International Proceedings in Informatics. 2020, 176 32:1-32:18. | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2755711 | |
dc.description.abstract | 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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Low-Rank Binary Matrix Approximation in Column-Sum Norm | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2020 The Authors | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.APPROX/RANDOM.2020.32 | |
dc.identifier.cristin | 1864764 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.40 | 176 | |
dc.source.pagenumber | 32:1-32:18 | en_US |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2020, 176, 32:1-32:18 | en_US |
dc.source.volume | 176 | en_US |