# Co-Clustering under the Maximum Norm+
## 2 Formal Definitions and Preliminaries
### Problem Definition  
We follow the terminology of [PERSON] _et al._[2]. For a matrix \(\mathcal{A}\in\mathbb{R}^{m\times n}\), a _\((k,\ell)\)-co-clustering_ is a pair \((\mathcal{I},\mathcal{J})\) consisting of a _\(k\)-partition_\(\mathcal{I}=\{I_{1},\ldots,I_{k}\}\) of the row indices \([m]\) of \(\mathcal{A}\) (that is, \(I_{i}\subseteq[m]\) for all \(1\leq i\leq k\), \(I_{i}\cap I_{j}=\emptyset\) for all \(1\leq i<j\leq k\) and \(\bigcup_{i=1}^{k}I_{i}=[m]\)) and an \(\ell\)-partition \(\mathcal{J}=\{J_{1},\ldots,J_{\ell}\}\) of the column indices \([n]\) of \(\mathcal{A}\). We call the elements of \(\mathcal{I}\) (resp., \(\mathcal{J}\)) row blocks (column blocks, resp.). Additionally, we require \(\mathcal{I}\) and \(\mathcal{J}\) to not contain empty sets. For \((r,s)\in[k]\times[\ell]\), the set \(\mathcal{A}_{rs}:=\{a_{ij}\in\mathcal{A}\mid(i,j)\in I_{r}\times J_{s}\}\) is called a _cluster_. The cost of a co-clustering (under maximum norm, which is the only norm we consider here) is defined as the maximum difference between any two entries in any cluster, formally \(\operatorname{cost}_{\infty}(\mathcal{I},\mathcal{J}):=\max_{(r,s)\in[k] \times[\ell]}(\max\mathcal{A}_{rs}-\min\mathcal{A}_{rs})\). Herein, \(\max\mathcal{A}_{rs}\) (\(\min\mathcal{A}_{rs}\)) denotes the maximum (minimum, resp.) entry in \(\mathcal{A}_{rs}\). The decision variant of Co-Clustering\({}_{\mathcal{L}}\) with maximum norm is as follows. Co-Clustering\({}_{\infty}\)  
**Input:** A matrix \(\mathcal{A}\in\mathbb{R}^{m\times n}\), integers \(k,\ell\in\mathbb{N}\) and a cost \(c\geq 0\). **Question:** Is there a \((k,\ell)\)-co-clustering \((\mathcal{I},\mathcal{J})\) of \(\mathcal{A}\) with \(\operatorname{cost}_{\infty}(\mathcal{I},\mathcal{J})\leq c\)? See Figure 1 for an introductory example. We define \(\Sigma:=\{a_{ij}\in\mathcal{A}\mid(i,j)\in[m]\times[n]\}\) to be the _alphabet_ of the input matrix \(\mathcal{A}\) (consisting of the numerical values that occur in \(\mathcal{A}\)). Note that \(|\Sigma|\ \leq\ mn\). We use the abbreviation \((k,\ell)\)-Co-Clustering\({}_{\infty}\) to refer to Co-Clustering\({}_{\infty}\) with constants \(k,\ell\in\mathbb{N}\), and by \((k,*)\)-Co-Clustering\({}_{\infty}\), we refer to the case where only \(k\) is constant and \(\ell\) is part of the input. Clearly, Co-Clustering\({}_{\infty}\) is symmetric with respect to \(k\) and \(\ell\) in the sense that any \((k,\ell)\)-co-clustering of a matrix \(\mathcal{A}\) is equivalent to an \((\ell,k)\)-co-clustering of the transposed matrix \(\mathcal{A}^{\mathcal{T}}\). Hence, we always assume that \(k\leq\ell\). We next collect some simple observations. First, determining whether there is a cost-zero (perfect) co-clustering is easy. Moreover, since, for a binary alphabet, the only interesting case is a perfect co-clustering, we get the following. **Observation 1**: Co-Clustering\({}_{\infty}\) _is solvable in \(O(mn)\) time for cost zero and also for any size-two alphabet._  
Let \((\mathcal{A},k,\ell,0)\) be a Co-Clustering\({}_{\infty}\) input instance. For a \((k,\ell)\)-co-clustering with cost zero, it holds that all entries of a cluster are equal. This is only possible if there are at most \(k\) different rows and at most \(\ell\) different columns in \(\mathcal{A}\), since otherwise, there will be a cluster containing two different entries. Thus, the case \(c=0\) can be solved by lexicographically sorting the rows and columns of \(\mathcal{A}\) in \(O(mn)\) time (e.g., using radix sort). Figure 1: The example shows two \((2,2)\)-co-clusterings (middle and right) of the same matrix \(\mathcal{A}\) (left-hand side). It demonstrates that by sorting rows and columns according to the co-clustering, the clusters can be illustrated as submatrices of this (permuted) input matrix. The cost of the \((2,2)\)-co-clustering in the middle is three (because of the two left clusters), and that of the \((2,2)\)-co-clustering on the right-hand side is one.