{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T16:42:43Z","timestamp":1778863363274,"version":"3.51.4"},"reference-count":78,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T00:00:00Z","timestamp":1577923200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T00:00:00Z","timestamp":1577923200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["263317"],"award-info":[{"award-number":["263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["263317"],"award-info":[{"award-number":["263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["249994"],"award-info":[{"award-number":["249994"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s10618-019-00669-5","type":"journal-article","created":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T13:14:09Z","timestamp":1577970849000},"page":"478-532","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Parameterized low-rank binary matrix approximation"],"prefix":"10.1007","volume":"34","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,2]]},"reference":[{"issue":"4","key":"669_CR1","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/1008731.1008736","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal PK, Har-Peled S, Varadarajan KR (2004) Approximating extent measures of points. J ACM 51(4):606\u2013635","journal-title":"J ACM"},{"key":"669_CR2","doi-asserted-by":"crossref","unstructured":"Aho AV, Ullman JD, Yannakakis M (1983) On notions of information transfer in VLSI circuits. In: Proceedings of the 15th annual ACM symposium on theory of computing (STOC), ACM, pp 133\u2013139","DOI":"10.1145\/800061.808742"},{"issue":"1","key":"669_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1006\/jagm.1999.1024","volume":"33","author":"N Alon","year":"1999","unstructured":"Alon N, Sudakov B (1999) On two segmentation problems. J Algorithms 33(1):173\u2013184","journal-title":"J Algorithms"},{"issue":"4","key":"669_CR4","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon N, Yuster R, Zwick U (1995) Color-coding. J ACM 42(4):844\u2013856","journal-title":"J ACM"},{"key":"669_CR5","doi-asserted-by":"crossref","unstructured":"Arora S, Ge R, Kannan R, Moitra A (2012) Computing a nonnegative matrix factorization\u2014provably. In: Proceedings of the 44th annual ACM symposium on theory of computing (STOC), ACM, pp 145\u2013162","DOI":"10.1145\/2213977.2213994"},{"key":"669_CR6","doi-asserted-by":"crossref","unstructured":"Badoiu M, Har-Peled S, Indyk P (2002) Approximate clustering via core-sets. In: Proceedings of the 34th annual ACM symposium on theory of computing (STOC). ACM, pp 250\u2013257","DOI":"10.1145\/509907.509947"},{"key":"669_CR7","unstructured":"Ban F, Bhattiprolu V, Bringmann K, Kolev P, Lee E, Woodruff DP (2019) A PTAS for $$\\ell _p$$-low rank approximation. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, California, USA, 6\u20139 Jan 2019. SIAM, pp 747\u2013766"},{"issue":"2","key":"669_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s10472-010-9185-y","volume":"59","author":"E Bartl","year":"2010","unstructured":"Bartl E, Belohl\u00e1vek R, Konecny J (2010) Optimal decompositions of matrices with grades into binary and graded matrices. Ann Math Artif Intell 59(2):151\u2013167","journal-title":"Ann Math Artif Intell"},{"key":"669_CR9","unstructured":"Basu A, Dinitz M, Li X (2016) Computing approximate PSD factorizations. CoRR arXiv:1602.07351"},{"issue":"1","key":"669_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jcss.2009.05.002","volume":"76","author":"R Belohl\u00e1vek","year":"2010","unstructured":"Belohl\u00e1vek R, Vychodil V (2010) Discovery of optimal factors in binary data via a novel method of matrix decomposition. J Comput Syst Sci 76(1):3\u201320","journal-title":"J Comput Syst Sci"},{"issue":"8","key":"669_CR11","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender HL, Downey RG, Fellows MR, Hermelin D (2009) On problems without polynomial kernels. J Comput Syst Sci 75(8):423\u2013434","journal-title":"J Comput Syst Sci"},{"key":"669_CR12","unstructured":"Boucher C, Lo C, Lokshtanov D (2011) Outlier detection for DNA fragment assembly. CoRR arXiv:1111.0376"},{"key":"669_CR13","unstructured":"Bringmann K, Kolev P, Woodruff DP (2017) Approximation algorithms for $$\\ell _0$$-low rank approximation. In: Advances in neural information processing systems 30 (NIPS), pp 6651\u20136662"},{"issue":"3","key":"669_CR14","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1970392.1970395","volume":"58","author":"EJ Cand\u00e8s","year":"2011","unstructured":"Cand\u00e8s EJ, Li X, Ma Y, Wright J (2011) Robust principal component analysis? J ACM 58(3):11:1\u201311:37","journal-title":"J ACM"},{"key":"669_CR15","unstructured":"Chandran LS, Issac D, Karrenbauer A (2016) On the parameterized complexity of biclique cover and partition. In: Proceedings of the 11th international symposium on parameterized and exact computation (IPEC), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol\u00a063, pp 11:1\u201311:13"},{"issue":"2","key":"669_CR16","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/090761793","volume":"21","author":"V Chandrasekaran","year":"2011","unstructured":"Chandrasekaran V, Sanghavi S, Parrilo PA, Willsky AS (2011) Rank-sparsity incoherence for matrix decomposition. SIAM J Optim 21(2):572\u2013596","journal-title":"SIAM J Optim"},{"key":"669_CR17","doi-asserted-by":"publisher","DOI":"10.1002\/9780470747278","volume-title":"Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation","author":"A Cichocki","year":"2009","unstructured":"Cichocki A, Zdunek R, Phan AH, Si Amari (2009) Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation. Wiley, Hoboken"},{"issue":"1","key":"669_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00453-007-0029-z","volume":"49","author":"R Cilibrasi","year":"2007","unstructured":"Cilibrasi R, van Iersel L, Kelk S, Tromp J (2007) The complexity of the single individual SNP haplotyping problem. Algorithmica 49(1):13\u201336","journal-title":"Algorithmica"},{"key":"669_CR19","unstructured":"Clarkson KL, Woodruff DP (2015) Input sparsity and hardness for robust subspace approximation. In: Proceedings of the 56th annual symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, pp 310\u2013329"},{"key":"669_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0024-3795(93)90224-C","volume":"190","author":"JE Cohen","year":"1993","unstructured":"Cohen JE, Rothblum UG (1993) Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl 190:149\u2013168","journal-title":"Linear Algebra Appl"},{"key":"669_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin"},{"key":"669_CR22","unstructured":"Dan C, Hansen KA, Jiang H, Wang L, Zhou Y (2015) On low rank approximation of binary matrices. CoRR arXiv:1511.01699"},{"key":"669_CR23","unstructured":"Downey RG, Fellows MR (1992) Fixed-parameter tractability and completeness. In: Proceedings of the 21st Manitoba conference on numerical mathematics and computing Congressus Numerantium, vol 87, pp 161\u2013178"},{"key":"669_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in computer science","author":"RG Downey","year":"2013","unstructured":"Downey RG, Fellows MR (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer, Berlin"},{"key":"669_CR25","unstructured":"Drange PG, Reidl F, Villaamil FS, Sikdar S (2015) Fast biclustering by dual parameterization. CoRR arXiv:1507.08158"},{"key":"669_CR26","unstructured":"Feige U (2014) NP-hardness of hypercube 2-segmentation. CoRR arXiv:1411.0821"},{"issue":"2","key":"669_CR27","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini S, Massar S, Pokutta S, Tiwary HR, de Wolf R (2015) Exponential lower bounds for polytopes in combinatorial optimization. J ACM 62(2):17","journal-title":"J ACM"},{"issue":"7","key":"669_CR28","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1016\/j.jcss.2014.04.015","volume":"80","author":"FV Fomin","year":"2014","unstructured":"Fomin FV, Kratsch S, Pilipczuk M, Pilipczuk M, Villanger Y (2014) Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J Comput Syst Sci 80(7):1430\u20131447","journal-title":"J Comput Syst Sci"},{"key":"669_CR29","doi-asserted-by":"crossref","unstructured":"Fomin FV, Golovach PA, Lokshtanov D, Panolan F, Saurabh S (2018a) Approximation schemes for low-rank binary matrix approximation problems. CoRR arXiv:1807.07156","DOI":"10.1145\/3365653"},{"issue":"2","key":"669_CR30","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/17M112258X","volume":"32","author":"FV Fomin","year":"2018","unstructured":"Fomin FV, Lokshtanov D, Meesum SM, Saurabh S, Zehavi M (2018b) Matrix rigidity from the viewpoint of parameterized complexity. SIAM J Discrete Math 32(2):966\u2013985","journal-title":"SIAM J Discrete Math"},{"key":"669_CR31","volume-title":"Kernelization. Theory of parameterized preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin FV, Lokshtanov D, Saurabh S, Zehavi M (2019) Kernelization. Theory of parameterized preprocessing. Cambridge University Press, Cambridge"},{"key":"669_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-12000-3","volume-title":"Low-rank and sparse modeling for visual analysis","author":"Y Fu","year":"2014","unstructured":"Fu Y (2014) Low-rank and sparse modeling for visual analysis, 1st edn. Springer, Berlin","edition":"1"},{"key":"669_CR33","doi-asserted-by":"crossref","unstructured":"Geerts F, Goethals B, Mielik\u00e4inen T (2004) Tiling databases. In: Proceedings of the 7th international conference on discovery science, (DS), pp 278\u2013289","DOI":"10.1007\/978-3-540-30214-8_22"},{"key":"669_CR34","unstructured":"Gillis N, Vavasis SA (2015) On the complexity of robust PCA and $$\\ell _1$$-norm low-rank matrix approximation. CoRR arXiv:1509.09236"},{"key":"669_CR35","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412236","author":"J Gramm","year":"2008","unstructured":"Gramm J, Guo J, H\u00fcffner F, Niedermeier R (2008) Data reduction and exact algorithms for clique cover. ACM J Exp Algorithmics. https:\/\/doi.org\/10.1145\/1412228.1412236","journal-title":"ACM J Exp Algorithmics"},{"issue":"1","key":"669_CR36","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(91)90006-6","volume":"51","author":"DA Gregory","year":"1991","unstructured":"Gregory DA, Pullman NJ, Jones KF, Lundgren JR (1991) Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J Comb Theory Ser B 51(1):73\u201389","journal-title":"J Comb Theory Ser B"},{"key":"669_CR37","unstructured":"Grigoriev D (1976) Using the notions of separability and independence for proving the lower bounds on the circuit complexity (in Russian). Notes of the Leningrad branch of the Steklov Mathematical Institute, Nauka"},{"issue":"5","key":"669_CR38","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1007\/BF01693976","volume":"14","author":"D Grigoriev","year":"1980","unstructured":"Grigoriev D (1980) Using the notions of separability and independence for proving the lower bounds on the circuit complexity. J Sov Math 14(5):1450\u20131456","journal-title":"J Sov Math"},{"issue":"8","key":"669_CR39","doi-asserted-by":"publisher","first-page":"1796","DOI":"10.1016\/j.sigpro.2011.10.003","volume":"92","author":"HW Gutch","year":"2012","unstructured":"Gutch HW, Gruber P, Yeredor A, Theis FJ (2012) ICA over finite fields\u2014separability and algorithms. Sig Process 92(8):1796\u20131808","journal-title":"Sig Process"},{"key":"669_CR40","unstructured":"Guterman AE (2008) Rank and determinant functions for matrices over semirings. In: Surveys in contemporary mathematics, London Mathematical Society lecture note series, vol 347. Cambridge University Press, Cambridge, pp 1\u201333"},{"key":"669_CR41","doi-asserted-by":"crossref","unstructured":"Inaba M, Katoh N, Imai H (1994) Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering. In: Proceedings of the 10th annual symposium on computational geometry. ACM, pp 332\u2013339","DOI":"10.1145\/177424.178042"},{"key":"669_CR42","doi-asserted-by":"crossref","unstructured":"Jiang P, Heath MT (2013) Mining discrete patterns via binary matrix factorization. In: ICDM workshops. IEEE Computer Society, pp 1129\u20131136","DOI":"10.1109\/ICDMW.2013.46"},{"key":"669_CR43","first-page":"281","volume-title":"A clustering approach to constrained binary matrix factorization","author":"P Jiang","year":"2014","unstructured":"Jiang P, Peng J, Heath M, Yang R (2014) A clustering approach to constrained binary matrix factorization. Springer, Berlin, pp 281\u2013303"},{"issue":"3\u20134","key":"669_CR44","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1561\/0400000025","volume":"4","author":"R Kannan","year":"2009","unstructured":"Kannan R, Vempala S (2009) Spectral algorithms. Found Trends Theor Comput Sci 4(3\u20134):157\u2013288","journal-title":"Found Trends Theor Comput Sci"},{"issue":"2","key":"669_CR45","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/972639.972644","volume":"51","author":"J Kleinberg","year":"2004","unstructured":"Kleinberg J, Papadimitriou C, Raghavan P (2004) Segmentation problems. J ACM 51(2):263\u2013280","journal-title":"J ACM"},{"key":"669_CR46","doi-asserted-by":"crossref","unstructured":"Koyut\u00fcrk M, Grama A (2003) Proximus: a framework for analyzing very high dimensional discrete-attributed datasets. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining (KDD). ACM, New York, pp 147\u2013156","DOI":"10.1145\/956750.956770"},{"issue":"2","key":"669_CR47","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar A, Sabharwal Y, Sen S (2010) Linear-time approximation schemes for clustering problems in any dimensions. J ACM 57(2):5:1\u20135:32","journal-title":"J ACM"},{"issue":"6755","key":"669_CR48","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1038\/44565","volume":"401","author":"DD Lee","year":"1999","unstructured":"Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Nature 401(6755):788\u2013791","journal-title":"Nature"},{"key":"669_CR49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000011","volume":"4","author":"SV Lokam","year":"2009","unstructured":"Lokam SV (2009) Complexity lower bounds using linear algebra. Found Trends Theor Comput Sci 4:1\u2013155","journal-title":"Found Trends Theor Comput Sci"},{"key":"669_CR50","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz L, Saks ME (1988) Lattices, m\u00f6bius functions and communication complexity. In: Proceedings of the 29th annual symposium on Foundations of Computer Science (FOCS). IEEE, pp 81\u201390","DOI":"10.1109\/SFCS.1988.21924"},{"key":"669_CR51","doi-asserted-by":"crossref","unstructured":"Lu H, Vaidya J, Atluri V (2008) Optimal boolean matrix decomposition: application to role engineering. In: Proceedings of the 24th international conference on data engineering, (ICDE), pp 297\u2013306","DOI":"10.1109\/ICDE.2008.4497438"},{"key":"669_CR52","doi-asserted-by":"crossref","unstructured":"Lu H, Vaidya J, Atluri V, Shin H, Jiang L (2011) Weighted rank-one binary matrix factorization. In: Proceedings of the eleventh SIAM international conference on data mining, SDM 2011, 28\u201330 Apr 2011, Mesa, Arizona, USA. SIAM\/Omnipress, pp 283\u2013294","DOI":"10.1137\/1.9781611972818.25"},{"issue":"5","key":"669_CR53","first-page":"655","volume":"9","author":"H Lu","year":"2012","unstructured":"Lu H, Vaidya J, Atluri V, Hong Y (2012) Constraint-aware role mining via extended boolean matrix decomposition. IEEE Trans Dependable Secur Comput 9(5):655\u2013669","journal-title":"IEEE Trans Dependable Secur Comput"},{"issue":"2","key":"669_CR54","first-page":"123","volume":"3","author":"MW Mahoney","year":"2011","unstructured":"Mahoney MW (2011) Randomized algorithms for matrices and data. Found Trends Mach Learn 3(2):123\u2013224","journal-title":"Found Trends Mach Learn"},{"issue":"4","key":"669_CR55","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/060673898","volume":"38","author":"D Marx","year":"2008","unstructured":"Marx D (2008) Closest substring problems with small distances. SIAM J Comput 38(4):1382\u20131410","journal-title":"SIAM J Comput"},{"key":"669_CR56","unstructured":"Meesum SM, Saurabh S (2016) Rank reduction of directed graphs by vertex and edge deletions. In: Proceedings of the 12th Latin American symposium on (LATIN), lecture notes in computer science, vol 9644. Springer, pp 619\u2013633"},{"key":"669_CR57","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2016.02.020","volume":"654","author":"SM Meesum","year":"2016","unstructured":"Meesum SM, Misra P, Saurabh S (2016) Reducing rank of the adjacency matrix by graph modification. Theoret Comput Sci 654:70\u201379","journal-title":"Theoret Comput Sci"},{"key":"669_CR58","doi-asserted-by":"crossref","unstructured":"Miettinen P, Vreeken J (2011) Model order selection for boolean matrix factorization. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining (KDD). ACM, pp 51\u201359","DOI":"10.1145\/2020408.2020424"},{"issue":"10","key":"669_CR59","doi-asserted-by":"publisher","first-page":"1348","DOI":"10.1109\/TKDE.2008.53","volume":"20","author":"P Miettinen","year":"2008","unstructured":"Miettinen P, Mielik\u00e4inen T, Gionis A, Das G, Mannila H (2008) The discrete basis problem. IEEE Trans Knowl Data Eng 20(10):1348\u20131362","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"4","key":"669_CR60","doi-asserted-by":"publisher","first-page":"50:1","DOI":"10.1145\/2871148","volume":"48","author":"B Mitra","year":"2016","unstructured":"Mitra B, Sural S, Vaidya J, Atluri V (2016) A survey of role mining. ACM Comput Surv 48(4):50:1\u201350:37","journal-title":"ACM Comput Surv"},{"issue":"1","key":"669_CR61","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1137\/140990139","volume":"45","author":"A Moitra","year":"2016","unstructured":"Moitra A (2016) An almost optimal algorithm for computing nonnegative rank. SIAM J Comput 45(1):156\u2013173","journal-title":"SIAM J Comput"},{"key":"669_CR62","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48331-2","volume-title":"Non-negative matrix factorization techniques","author":"GR Naik","year":"2016","unstructured":"Naik GR (2016) Non-negative matrix factorization techniques. Springer, Berlin"},{"key":"669_CR63","doi-asserted-by":"crossref","unstructured":"Naor M, Schulman LJ, Srinivasan A (1995) Splitters and near-optimal derandomization. In: Proceedings of the 36th annual symposium on Foundations of Computer Science (FOCS). IEEE, pp 182\u2013191","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"5","key":"669_CR64","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"39","author":"J Orlin","year":"1977","unstructured":"Orlin J (1977) Contentment in graph theory: covering graphs with cliques. Nederl Akad Wetensch Proc Ser A 80=Indag Math 39(5):406\u2013424","journal-title":"Nederl Akad Wetensch Proc Ser A 80=Indag Math"},{"issue":"2","key":"669_CR65","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/506147.506149","volume":"49","author":"R Ostrovsky","year":"2002","unstructured":"Ostrovsky R, Rabani Y (2002) Polynomial-time approximation schemes for geometric min-sum median clustering. J ACM 49(2):139\u2013156","journal-title":"J ACM"},{"issue":"2","key":"669_CR66","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1109\/TIT.2015.2510657","volume":"62","author":"A Painsky","year":"2016","unstructured":"Painsky A, Rosset S, Feder M (2016) Generalized independent component analysis over finite alphabets. IEEE Trans Inf Theory 62(2):1038\u20131053","journal-title":"IEEE Trans Inf Theory"},{"key":"669_CR67","unstructured":"Razborov AA (1989) On rigid matrices. Manuscript in Russian"},{"key":"669_CR68","doi-asserted-by":"crossref","unstructured":"Razenshteyn IP, Song Z, Woodruff DP (2016) Weighted low rank approximations with provable guarantees. In: Proceedings of the 48th annual ACM symposium on theory of computing (STOC). ACM, pp 250\u2013263","DOI":"10.1145\/2897518.2897639"},{"key":"669_CR69","doi-asserted-by":"crossref","unstructured":"Shen BH, Ji S, Ye J (2009) Mining discrete patterns via binary matrix factorization. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining (KDD). ACM, New York, pp 757\u2013766","DOI":"10.1145\/1557019.1557103"},{"key":"669_CR70","doi-asserted-by":"crossref","unstructured":"Shi Z, Wang L, Shi L (2014) Approximation method to rank-one binary matrix factorization. In: 2014 IEEE international conference on automation science and engineering, CASE 2014, New Taipei, Taiwan, 18\u201322 Aug 2014. IEEE, pp 800\u2013805","DOI":"10.1109\/CoASE.2014.6899417"},{"key":"669_CR71","doi-asserted-by":"crossref","unstructured":"Vaidya J (2012) Boolean matrix decomposition problem: theory, variations and applications to data engineering. In: Proceedings of the 28th IEEE international conference on data engineering (ICDE). IEEE Computer Society, pp 1222\u20131224","DOI":"10.1109\/ICDE.2012.144"},{"key":"669_CR72","doi-asserted-by":"crossref","unstructured":"Vaidya J, Atluri V, Guo Q (2007) The role mining problem: finding a minimal descriptive set of roles. In: Proceedings of the 12th ACM symposium on access control models and (SACMAT), pp 175\u2013184","DOI":"10.1145\/1266840.1266870"},{"key":"669_CR73","doi-asserted-by":"crossref","unstructured":"Valiant LG (1977) Graph-theoretic arguments in low-level complexity. In: Mathematical foundations of computer science (MFCS), Lecture Notes in Computer Science, vol\u00a053. Springer, pp 162\u2013176","DOI":"10.1007\/3-540-08353-7_135"},{"issue":"1\u20132","key":"669_CR74","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000060","volume":"10","author":"DP Woodruff","year":"2014","unstructured":"Woodruff DP (2014) Sketching as a tool for numerical linear algebra. Found Trends Theor Comput Sci 10(1\u20132):1\u2013157","journal-title":"Found Trends Theor Comput Sci"},{"key":"669_CR75","unstructured":"Wright J, Ganesh A, Rao SR, Peng Y, Ma Y (2009) Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: Proceedings of 23rd annual conference on neural information processing systems (NIPS). Curran Associates, Inc., pp 2080\u20132088"},{"key":"669_CR76","unstructured":"Wulff S, Urner R, Ben-David S (2013) Monochromatic bi-clustering. In: Proceedings of the 30th international conference on machine learning, (ICML), JMLR.org, JMLR workshop and conference proceedings, vol\u00a028, pp 145\u2013153"},{"issue":"3","key":"669_CR77","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J Comput Syst Sci 43(3):441\u2013466","journal-title":"J Comput Syst Sci"},{"issue":"8","key":"669_CR78","doi-asserted-by":"publisher","first-page":"5342","DOI":"10.1109\/TIT.2011.2145090","volume":"57","author":"A Yeredor","year":"2011","unstructured":"Yeredor A (2011) Independent component analysis over Galois fields of prime order. IEEE Trans Inf Theory 57(8):5342\u20135359","journal-title":"IEEE Trans Inf Theory"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-019-00669-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10618-019-00669-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-019-00669-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,24]],"date-time":"2023-09-24T16:06:44Z","timestamp":1695571604000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10618-019-00669-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,2]]},"references-count":78,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["669"],"URL":"https:\/\/doi.org\/10.1007\/s10618-019-00669-5","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,2]]},"assertion":[{"value":"21 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}