摘要：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.
