# Co-Clustering under the Maximum Norm+
## 1 Introduction  
Co-clustering, also known as _bi-clustering_[1], performs a simultaneous clustering of the rows and columns of a data matrix. Roughly speaking, the problem is, given a numerical input matrix \(\mathcal{A}\), to partition the rows and columns of \(\mathcal{A}\) into subsets minimizing a given _cost_ function (measuring \"homogeneity\"). For a given subset \(I\) of rows and a subset \(J\) of columns, the corresponding _cluster_ consists of all entries \(a_{ij}\) with \(i\in I\) and \(j\in J\). The cost function usually defines homogeneity in terms of distances (measured in some norm) between the entries of each cluster. Note that the variant where clusters are allowed to \"overlap\", meaning that some rows and columns are contained in multiple clusters, has also been studied [1]. We focus on the non-overlapping variant, which can be stated as follows. Co-Clustering  
**Input:** A matrix \(\mathcal{A}\in\mathbb{R}^{m\times n}\) and two positive integers \(k,\ell\in\mathbb{N}\). **Task:** Find a partition of \(\mathcal{A}\)'s rows into \(k\) subsets and a partition of \(\mathcal{A}\)'s columns into \(\ell\) subsets, such that a given cost function (defined with respect to some norm \(\mathcal{L}\)) is minimized for the corresponding clustering. Co-clustering is a fundamental paradigm for unsupervised data analysis. Its applications range from microarrays and bioinformatics over recommender systems to election analysis [1; 2; 3; 4]. Due to its enormous practical significance, there is a vast amount of literature discussing various variants; however, due to the observed NP-hardness of \"almost all interesting variants\" [1], most of the literature deals with heuristic, typically empirically-validated algorithms. Indeed, there has been very active research on co-clustering in terms of heuristic algorithms, while there is little substantial theoretical work for this important clustering problem. Motivated by an effort towards a deeper theoretical analysis, as started by [PERSON] _et al._[2], we further refine and strengthen the theoretical investigations on the computational complexity of a natural special case of Co-Clustering\({}_{\mathcal{L}}\), namely we study the case of \(\mathcal{L}\) being the maximum norm \(L_{\infty}\), where the problem comes down to minimizing the maximum distance between entries of a cluster. This cost function might be a reasonable choice in practice due to its outlier sensitivity. In network security, for example, there often exists a vast amount of \"normal\" data points, whereas there are only very few \"malicious\" data points, which are outliers with respect to certain attributes. The maximum norm does not allow one to put entries with large differences into the same cluster, which is crucial for detecting possible attacks. The maximum norm can also be applied in a discretized setting, where input values are grouped (for example, replaced by integer values) according to their level of deviation from the mean of the respective attribute. It is then not allowed to put values of different ranges of the standard deviation into the same cluster. Last, but not least, we study an even more restricted clustering version, where the partitions of the rows and columns have to contain consecutive subsets. This version subsumes the problem of feature discretization, which is used as a preprocessing technique in data mining applications [5; 6; 7]. See Section 3.3 for this version. [PERSON] _et al._[2] provided a thorough analysis of the polynomial-time approximability of Co-Clustering\({}_{\mathcal{L}}\) (with respect to \(L_{p}\)-norms), presenting several constant-factor approximation algorithms. While their algorithms are almost straightforward, relying on one-dimensionally clustering first the rows and then the columns, their main contribution lies in the sophisticated mathematical analysis of the corresponding approximation factors. Note that [PERSON] _et al._[8] further generalized this approach to higher dimensions, then called _tensor clustering_.