{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T10:43:09Z","timestamp":1771929789345,"version":"3.50.1"},"reference-count":19,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T00:00:00Z","timestamp":1456358400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/13"],"award-info":[{"award-number":["NI 369\/13"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Co-clustering, that is partitioning a numerical matrix into \u201chomogeneous\u201d submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from {0, 1, 2}.<\/jats:p>","DOI":"10.3390\/a9010017","type":"journal-article","created":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T10:24:25Z","timestamp":1456395865000},"page":"17","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Co-Clustering under the Maximum Norm"],"prefix":"10.3390","volume":"9","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[{"name":"IGM-LabInfo, CNRS UMR 8049, Universit\u00e9 Paris-Est Marne-la-Vall\u00e9e, 77454 Marne-la-Vall\u00e9e, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, 10587 TU Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sepp","family":"Hartung","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, 10587 TU Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Softwaretechnik und Theoretische Informatik, 10587 TU Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/TCBB.2004.2","article-title":"Biclustering Algorithms for Biological Data Analysis: A Survey","volume":"1","author":"Madeira","year":"2004","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.4086\/toc.2012.v008a026","article-title":"A Constant-Factor Approximation Algorithm for Co-clustering","volume":"8","author":"Anagnostopoulos","year":"2012","journal-title":"Theory Comput."},{"key":"ref_3","first-page":"1919","article-title":"A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation","volume":"8","author":"Banerjee","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"ref_4","unstructured":"Tanay, A., Sharan, R., and Shamir, R. (2005). Handbook of Computational Molecular Biology, Chapman & Hall\/CRC."},{"key":"ref_5","unstructured":"Nguyen, S.H., and Skowron, A. (October, January 28). Quantization Of Real Value Attributes-Rough Set and Boolean Reasoning Approach. Proceedings of the Second Joint Annual Conference on Information Sciences, Wrightsville Beach, NC, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., and Nguyen, S.H. (1998, January 22\u201326). On Finding Optimal Discretizations for Two Attributes. Proceedings of the First International Conference on Rough Sets and Current Trends in Computing (RSCTC\u201998), Warsaw, Poland.","DOI":"10.1007\/3-540-69115-4_74"},{"key":"ref_7","unstructured":"Nguyen, H.S. (2006). Transactions on Rough Sets V, Springer."},{"key":"ref_8","unstructured":"Jegelka, S., Sra, S., and Banerjee, A. (2009, January 3\u20135). Approximation Algorithms for Tensor Clustering. Proceedings of the 20th International Conference of Algorithmic Learning Theory (ALT\u201909), Porto, Portugal."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1080\/01621459.1972.10481214","article-title":"Direct clustering of a data matrix","volume":"67","author":"Hartigan","year":"1972","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_10","unstructured":"Califano, A., Stolovitzky, G., and Tu, Y. (2000, January 16\u201323). Analysis of Gene Expression Microarrays for Phenotype Classification. Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (ISMB\u201900), AAAI, San Diego, CA, USA."},{"key":"ref_11","unstructured":"Wulff, S., Urner, R., and Ben-David, S. (2013, January 16\u201321). Monochromatic Bi-Clustering. Proceedings of the 30th International Conference on Machine Learning (ICML\u201913), Atlanta, GA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer International Publishing.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_15","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","article-title":"Optimal Packing and Covering in the Plane are NP-Complete","volume":"12","author":"Fowler","year":"1981","journal-title":"Inf. Process. Lett."},{"key":"ref_17","first-page":"75","article-title":"PicoSAT Essentials","volume":"4","author":"Biere","year":"2008","journal-title":"J. Satisf. Boolean Model. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1109\/TPAMI.2013.140","article-title":"Attribute-Based Classification for Zero-Shot Visual Object Categorization","volume":"36","author":"Lampert","year":"2013","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","article-title":"A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas","volume":"8","author":"Aspvall","year":"1979","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/17\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:19:42Z","timestamp":1760210382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/1\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,25]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,3]]}},"alternative-id":["a9010017"],"URL":"https:\/\/doi.org\/10.3390\/a9010017","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,25]]}}}