{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:06Z","timestamp":1750220886114,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union's Horizon 2020 research and innovation programme","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"name":"Norwegian Research Council via grants MULTIVAL and CLASSIS"},{"name":"European Research Council"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            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 time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are L\n            <jats:sc>ow<\/jats:sc>\n            GF(2)-R\n            <jats:sc>ank<\/jats:sc>\n            A\n            <jats:sc>pproximation<\/jats:sc>\n            , L\n            <jats:sc>ow<\/jats:sc>\n            B\n            <jats:sc>oolean<\/jats:sc>\n            -R\n            <jats:sc>ank<\/jats:sc>\n            A\n            <jats:sc>pproximation<\/jats:sc>\n            , and various versions of B\n            <jats:sc>inary<\/jats:sc>\n            C\n            <jats:sc>lustering<\/jats:sc>\n            . For example, for L\n            <jats:sc>ow<\/jats:sc>\n            GF(2)-R\n            <jats:sc>ank<\/jats:sc>\n            A\n            <jats:sc>pproximation<\/jats:sc>\n            problem, where for an\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            binary matrix\n            <jats:italic>A<\/jats:italic>\n            and integer\n            <jats:italic>r<\/jats:italic>\n            &gt; 0, we seek for a binary matrix\n            <jats:italic>B<\/jats:italic>\n            of GF(2) rank at most\n            <jats:italic>r<\/jats:italic>\n            such that the \u2113\n            <jats:sub>0<\/jats:sub>\n            -norm of matrix A\u2212B is minimum, our algorithm, for any \u03f5 &gt; 0 in time\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\u03f5)\u22c5\n            <jats:italic>n<\/jats:italic>\n            \u22c5\n            <jats:italic>m<\/jats:italic>\n            , where\n            <jats:italic>f<\/jats:italic>\n            is some computable function, outputs a (1+\u03f5)-approximate solution with probability at least (1\u22121\\\n            <jats:italic>e<\/jats:italic>\n            ). This is the first linear time approximation scheme for these problems. We also give (deterministic) PTASes for these problems running in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>f<\/jats:italic>\n              (\n              <jats:italic>r<\/jats:italic>\n              )1\\\u03f5\n              <jats:sup>2<\/jats:sup>\n              log 1\\\u03f5\n            <\/jats:sup>\n            , where\n            <jats:italic>f<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3365653","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Approximation Schemes for Low-rank Binary Matrix Approximation Problems"],"prefix":"10.1145","volume":"16","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Hyderabad, Kandi, Sangareddy, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Tharamani, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1024"},{"volume-title":"The Bicluster Graph Editing Problem. Master\u2019s thesis","author":"Amit Noga","key":"e_1_2_1_3_1","unstructured":"Noga Amit . 2004. The Bicluster Graph Editing Problem. Master\u2019s thesis . Tel Aviv University . Noga Amit. 2004. The Bicluster Graph Editing Problem. Master\u2019s thesis. Tel Aviv University."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213994"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19)","author":"Ban F.","key":"e_1_2_1_6_1","unstructured":"F. Ban , V. Bhattiprolu , K. Bringmann , P. Kolev , E. Lee , and D. P. Woodruff . 2019. A PTAS for &ell;p-low rank approximation . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19) . 747--766. F. Ban, V. Bhattiprolu, K. Bringmann, P. Kolev, E. Lee, and D. P. Woodruff. 2019. A PTAS for &ell;p-low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19). 747--766."},{"key":"e_1_2_1_7_1","first-page":"2","article-title":"Optimal decompositions of matrices with grades into binary and graded matrices","volume":"59","author":"Bartl Eduard","year":"2010","unstructured":"Eduard Bartl , Radim Belohl\u00e1vek , and Jan Konecny . 2010 . Optimal decompositions of matrices with grades into binary and graded matrices . Ann. Math. Artific. Intell. 59 , 2 (June 2010), 151--167. DOI:https:\/\/doi.org\/10.1007\/s10472-010-9185-y 10.1007\/s10472-010-9185-y Eduard Bartl, Radim Belohl\u00e1vek, and Jan Konecny. 2010. Optimal decompositions of matrices with grades into binary and graded matrices. Ann. Math. Artific. Intell. 59, 2 (June 2010), 151--167. DOI:https:\/\/doi.org\/10.1007\/s10472-010-9185-y","journal-title":"Ann. Math. Artific. Intell."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.05.002"},{"volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201917)","author":"Bringmann Karl","key":"e_1_2_1_9_1","unstructured":"Karl Bringmann , Pavel Kolev , and David P. Woodruff . 2017. Approximation algorithms for &ell;0-low rank approximation . In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201917) . 6651--6662. Retrieved from http:\/\/papers.nips.cc\/paper\/7242-approximation-algorithms-for-ell_0-low-rank-approximation. Karl Bringmann, Pavel Kolev, and David P. Woodruff. 2017. Approximation algorithms for &ell;0-low rank approximation. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS\u201917). 6651--6662. Retrieved from http:\/\/papers.nips.cc\/paper\/7242-approximation-algorithms-for-ell_0-low-rank-approximation."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916)","volume":"63","author":"Chandran L. Sunil","year":"2016","unstructured":"L. Sunil Chandran , Davis Issac , and Andreas Karrenbauer . 2016 . On the parameterized complexity of biclique cover and partition . In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916) (LIPIcs), Vol. 63 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 11:1--11:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC. 2016.11 10.4230\/LIPIcs.IPEC.2016.11 L. Sunil Chandran, Davis Issac, and Andreas Karrenbauer. 2016. On the parameterized complexity of biclique cover and partition. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC\u201916) (LIPIcs), Vol. 63. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 11:1--11:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.11"},{"volume-title":"Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS\u201915)","author":"Kenneth","key":"e_1_2_1_11_1","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2015. Input sparsity and hardness for robust subspace approximation . In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS\u201915) . IEEE Computer Society, 310--329. Kenneth L. Clarkson and David P. Woodruff. 2015. Input sparsity and hardness for robust subspace approximation. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS\u201915). IEEE Computer Society, 310--329."},{"key":"e_1_2_1_12_1","volume-title":"He Jiang, Liwei Wang, and Yuchen Zhou.","author":"Dan Chen","year":"2015","unstructured":"Chen Dan , Kristoffer Arnsfelt Hansen , He Jiang, Liwei Wang, and Yuchen Zhou. 2015 . On low rank approximation of binary matrices. CoRR abs\/1511.01699 (2015). Retrieved from http:\/\/arxiv.org\/abs\/1511.01699. Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. 2015. On low rank approximation of binary matrices. CoRR abs\/1511.01699 (2015). Retrieved from http:\/\/arxiv.org\/abs\/1511.01699."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Fomin Fedor V.","year":"2018","unstructured":"Fedor V. Fomin , Petr A. Golovach , and Fahad Panolan . 2018 . Parameterized low-rank binary matrix approximation . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . (LIPIcs), Vol. 107 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 53:1--53:16. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2018.53 10.4230\/LIPIcs.ICALP.2018.53 Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan. 2018. Parameterized low-rank binary matrix approximation. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). (LIPIcs), Vol. 107. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 53:1--53:16. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.53"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/iCECE.2010.1455"},{"key":"e_1_2_1_15_1","volume-title":"Vavasis","author":"Gillis Nicolas","year":"2015","unstructured":"Nicolas Gillis and Stephen A . Vavasis . 2015 . On the complexity of robust PCA and &ell;1-norm low-rank matrix approximation. CoRR abs\/1509.09236 (2015). Retrieved from http:\/\/arxiv.org\/abs\/1509.09236. Nicolas Gillis and Stephen A. Vavasis. 2015. On the complexity of robust PCA and &ell;1-norm low-rank matrix approximation. CoRR abs\/1509.09236 (2015). Retrieved from http:\/\/arxiv.org\/abs\/1509.09236."},{"key":"e_1_2_1_16_1","volume-title":"Data reduction and exact algorithms for clique cover. ACM J. Exper. Alg. 13","author":"Gramm Jens","year":"2008","unstructured":"Jens Gramm , Jiong Guo , Falk H\u00fcffner , and Rolf Niedermeier . 2008. Data reduction and exact algorithms for clique cover. ACM J. Exper. Alg. 13 ( 2008 ). DOI:https:\/\/doi.org\/10.1145\/1412228.1412236 10.1145\/1412228.1412236 Jens Gramm, Jiong Guo, Falk H\u00fcffner, and Rolf Niedermeier. 2008. Data reduction and exact algorithms for clique cover. ACM J. Exper. Alg. 13 (2008). DOI:https:\/\/doi.org\/10.1145\/1412228.1412236"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90006-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2011.10.003"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"volume-title":"Proceedings of the Industrial Conference on Data Mining Workshops (ICDM\u201913)","author":"Jiang Peng","key":"e_1_2_1_20_1","unstructured":"Peng Jiang and Michael T. Heath . 2013. Mining discrete patterns via binary matrix factorization . In Proceedings of the Industrial Conference on Data Mining Workshops (ICDM\u201913) . IEEE Computer Society, 1129--1136. Peng Jiang and Michael T. Heath. 2013. Mining discrete patterns via binary matrix factorization. In Proceedings of the Industrial Conference on Data Mining Workshops (ICDM\u201913). IEEE Computer Society, 1129--1136."},{"volume-title":"Data Mining and Knowledge Discovery for Big Data: Methodologies, Challenge and Opportunities","author":"Jiang Peng","key":"e_1_2_1_21_1","unstructured":"Peng Jiang , Jiming Peng , Michael Heath , and Rui Yang . 2014. A clustering approach to constrained binary matrix factorization . In Data Mining and Knowledge Discovery for Big Data: Methodologies, Challenge and Opportunities . Springer Berlin , 281--303. Peng Jiang, Jiming Peng, Michael Heath, and Rui Yang. 2014. A clustering approach to constrained binary matrix factorization. In Data Mining and Knowledge Discovery for Big Data: Methodologies, Challenge and Opportunities. Springer Berlin, 281--303."},{"key":"e_1_2_1_22_1","first-page":"3","article-title":"Spectral algorithms","volume":"4","author":"Kannan Ravindran","year":"2009","unstructured":"Ravindran Kannan and Santosh Vempala . 2009 . Spectral algorithms . Found. Trends Theor. Comput. Sci. 4 , 3 -- 4 (2009), 157--288. DOI:https:\/\/doi.org\/10.1561\/0400000025 10.1561\/0400000025 Ravindran Kannan and Santosh Vempala. 2009. Spectral algorithms. Found. Trends Theor. Comput. Sci. 4, 3--4 (2009), 157--288. DOI:https:\/\/doi.org\/10.1561\/0400000025","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972644"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956770"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2012.21"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.53"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020424"},{"key":"e_1_2_1_30_1","volume-title":"Article 50 (Feb.","author":"Mitra Barsha","year":"2016","unstructured":"Barsha Mitra , Shamik Sural , Jaideep Vaidya , and Vijayalakshmi Atluri . 2016. A survey of role mining. ACM Comput. Surv. 48, 4 , Article 50 (Feb. 2016 ), 37 pages. DOI:https:\/\/doi.org\/10.1145\/2871148 10.1145\/2871148 Barsha Mitra, Shamik Sural, Jaideep Vaidya, and Vijayalakshmi Atluri. 2016. A survey of role mining. ACM Comput. Surv. 48, 4, Article 50 (Feb. 2016), 37 pages. DOI:https:\/\/doi.org\/10.1145\/2871148"},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","key":"e_1_2_1_31_1","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press , New York, NY . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990139"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506149"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2510657"},{"volume-title":"Proceedings of the 48th ACM Symposium on Theory of Computing (STOC\u201916)","author":"Razenshteyn Ilya P.","key":"e_1_2_1_35_1","unstructured":"Ilya P. Razenshteyn , Zhao Song , and David P. Woodruff . 2016. Weighted low rank approximations with provable guarantees . In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC\u201916) . ACM, 250--263. DOI:https:\/\/doi.org\/10.1145\/2897518.2897639 10.1145\/2897518.2897639 Ilya P. Razenshteyn, Zhao Song, and David P. Woodruff. 2016. Weighted low rank approximations with provable guarantees. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC\u201916). ACM, 250--263. DOI:https:\/\/doi.org\/10.1145\/2897518.2897639"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557103"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.144"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1266840.1266870"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning (ICML\u201913) (JMLR Workshop and Conference Proceedings)","volume":"28","author":"Wulff Sharon","year":"2013","unstructured":"Sharon Wulff , Ruth Urner , and Shai Ben-David . 2013 . Monochromatic bi-clustering . In Proceedings of the 30th International Conference on Machine Learning (ICML\u201913) (JMLR Workshop and Conference Proceedings) , Vol. 28 . JMLR.org, 145--153. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v28\/. Sharon Wulff, Ruth Urner, and Shai Ben-David. 2013. Monochromatic bi-clustering. In Proceedings of the 30th International Conference on Machine Learning (ICML\u201913) (JMLR Workshop and Conference Proceedings), Vol. 28. JMLR.org, 145--153. Retrieved from http:\/\/jmlr.org\/proceedings\/papers\/v28\/."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2145090"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365653","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:21Z","timestamp":1750203861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3365653"],"URL":"https:\/\/doi.org\/10.1145\/3365653","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}