# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Polynomial-Time Solvability  
We first present a simple and efficient algorithm for \((1,*)\)-Co-Clustering\({}_{\infty}\), that is the variant where all rows belong to one row block. **Theorem 4**. : \((1,*)\)-Co-Clustering\({}_{\infty}\) _is solvable in \(O(n(m+\log n))\) time._  
Proof. : We show that Algorithm 1 solves \((1,*)\)-Co-Clustering\({}_{\infty}\). In fact, it even computes the minimum \(\ell^{\prime}\), such that \(\mathcal{A}\) has a \((1,\ell^{\prime})\)-co-clustering of cost \(c\). The overall idea is that with only one row block all entries of a column \(j\) are contained in a cluster in any solution, and thus, it suffices to consider only the minimum \(\alpha_{j}\) and the maximum \(\beta_{j}\) value in column \(j\). More precisely, for a column block \(J\subseteq[n]\) of a solution, it follows that \(\max\{\beta_{j}\mid j\in J\}-\min\{\alpha_{j}\mid j\in J\}\leq c\). The algorithm starts with the column \(j_{1}\) that contains the overall minimum value \(\alpha_{j_{1}}\) of the input matrix, that is \(\alpha_{j_{1}}=\min\{\alpha_{j}\mid j\in[n]\}\). Clearly, \(j_{1}\) has to be contained in some column block, say \(J_{1}\). The algorithm then adds all other columns \(j\) to \(J_{1}\) where \(\beta_{j}\leq\alpha_{j_{1}}+c\), removes the columns \(J_{1}\) from the matrix and recursively proceeds with the column containing the minimum value of the remaining matrix. We continue with the correctness of the described procedure. ```
Input:\(\mathcal{A}\in\mathbb{R}^{m\times n}\), \(\ell\geq 1\), \(c\geq 0\). Output: A partition of \([n]\) into at most \(\ell\) blocks yielding a cost of at most \(c\), or no if no such partition exists. for\(j\gets 1\)to\(n\)do \(\alpha_{j}\leftarrow\min\{a_{ij}\mid 1\leq i\leq m\}\); \(\beta_{j}\leftarrow\max\{a_{ij}\mid 1\leq i\leq m\}\); if\(\beta_{j}-\alpha_{j}>c\)then returnno; \(\mathcal{N}\leftarrow[n]\); for\(s\gets 1\)to\(\ell\)do  Let \(j_{s}\in\mathcal{N}\) be the index such that \(\alpha_{j_{s}}\) is minimal; \(J_{s}\leftarrow\{j\in\mathcal{N}\mid\beta_{j}-\alpha_{j_{s}}\leq c\}\); \(\mathcal{N}\leftarrow\mathcal{N}\setminus J_{s}\); if\(\mathcal{N}=\emptyset\)then return\((J_{1},\ldots,J_{s})\); returnno;
```  
**Algorithm 1**Algorithm for \((1,*)\)-Co-Clustering\({}_{\infty}\). If Algorithm 1 returns \((J_{1},\ldots,J_{\ell^{\prime}})\) at Line 1, then this is a column partition into \(\ell^{\prime}\leq\ell\) blocks satisfying the cost constraint. First, it is a partition by construction: the sets \(J_{s}\) are successively removed from \(\mathcal{N}\) until it is empty. Now, let \(s\in[\ell^{\prime}]\). Then, for all \(j\in J_{s}\), it holds \(\alpha_{j}\geq\alpha_{j_{s}}\) (by definition of \(j_{s}\)) and \(\beta_{j}\leq\alpha_{j_{s}}+c\) (by definition of \(J_{s}\)). Thus, \(\mathcal{A}_{1s}\subseteq[\alpha_{j_{s}},\alpha_{j_{s}}+c]\) holds for all \(s\in[\ell^{\prime}]\), which yields \(\mathrm{cost}_{\infty}(\{[m]\},\{J_{1},\ldots,J_{\ell^{\prime}}\})\leq c\). Otherwise, if Algorithm 1 returns no in Line 5, then it is clearly a no-instance, since the difference between the maximum and the minimum value in a column is larger than \(c\). If no is returned in Line 13, then the algorithm has computed column indices \(j_{s}\) and column blocks \(J_{s}\) for each \(s\in[\ell]\), and there still exists at least one index \(j_{\ell+1}\) in \(\mathcal{N}\) when the algorithm terminates. We claim that the columns \(j_{1},\ldots,j_{\ell+1}\) all have to be in different blocks in any solution. To see this, consider any \(s,s^{\prime}\in[\ell+1]\) with \(s<s^{\prime}\). By construction, \(j_{s^{\prime}}\
otin J_{s}\). Therefore, \(\beta_{j_{s^{\prime}}}>\alpha_{j_{s}}+c\) holds, and columns \(j_{s}\) and \(j_{s^{\prime}}\) contain elements with distance more than \(c\). Thus, in any co-clustering with cost at most \(c\), columns \(j_{1},\ldots,j_{\ell+1}\) must be in different blocks, which is impossible with only \(\ell\) blocks. Hence, we indeed have a no-instance. The time complexity is seen as follows.