# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Polynomial-Time Solvability
The first loop examines in \(O(mn)\) time all elements of the matrix. The second loop can be performed in \(O(n)\) time if the \(\alpha_{j}\) and the \(\beta_{j}\) are sorted beforehand, requiring \(O(n\log n)\) time. Overall, the running time is in \(O(n(m+\log n))\). From now on, we focus on the \(k=2\) case, that is we need to partition the rows into two blocks. We first consider the simplest case, where also \(\ell=2\). **Theorem 5**: \((2,2)\)_-Co-Clustering\({}_{\infty}\) is solvable in \(O(|\Sigma|^{2}mn)\) time._  
We use the reduction to CNF-SAT provided by Lemma 1. First, note that a cluster boundary \(\mathcal{U}\in\Sigma^{2\times 2}\) can only be satisfied if it contains the elements \(\min\Sigma\) and \(\min\{a\in\Sigma\mid a\geq\max\Sigma-c\}\). The algorithm enumerates all \(O(|\Sigma|^{2})\) of these cluster boundaries. For a fixed \(\mathcal{U}\), we construct the Boolean formula \(\phi_{\mathcal{A}\mathcal{U}}\). Observe that this formula is in two-CNF form: The formula consists of \(k\)-clauses, \(\ell\)-clauses and \(2\)-clauses, and we have \(k=\ell=2\). Hence, we can determine whether it is satisfiable in linear time [19] (note that the size of the formula is in \(O(mn)\)). Overall, the input is a yes-instance if and only if \(\phi_{\mathcal{A}\mathcal{U}}\) is satisfiable for some cluster boundary \(\mathcal{U}\). Finally, we show that it is possible to extend the above result to any number of column blocks for size-three alphabets. **Theorem 6**: \((2,*)\)_-Co-Clustering\({}_{\infty}\) is \(O(mn)\)-time solvable for \(|\Sigma|=3\)._  
Let \(I=(\mathcal{A}\in\{\alpha,\beta,\gamma\}^{m\times n},k=2,\ell,c)\) be a \((2,*)\)-Co-Clustering\({}_{\infty}\) instance. We assume without loss of generality that \(\alpha<\beta<\gamma\). The case \(\ell\leq 2\) is solvable in \(O(mn)\) time by Theorem 5. Hence, it remains to consider the case \(\ell\geq 3\). As \(|\Sigma|=3\), there are four potential values for a minimum-cost \((2,\ell)\)-co-clustering. Namely, cost zero (all cluster entries are equal), cost \(\beta-\alpha\), cost \(\gamma-\beta\) and cost \(\gamma-\alpha\). Since any \((2,\ell)\)-co-clustering is of cost at most \(\gamma-\alpha\) and because it can be checked in \(O(mn)\) time whether there is a \((2,\ell)\)-co-clustering of cost zero (Observation 1), it remains to check whether there is a \((2,\ell)\)-co-clustering between these two extreme cases, that is for \(c\in\{\beta-\alpha,\gamma-\beta\}\). Avoiding a pair \((x,y)\in\{\alpha,\beta,\gamma\}^{2}\) means to find a co-clustering without a cluster containing \(x\) and \(y\). If \(c=\max\{\beta-\alpha,\gamma-\beta\}\) (Case 1), then the problem comes down to finding a \((2,\ell)\)-co-clustering avoiding the pair \((\alpha,\gamma)\). Otherwise (Case 2), the problem is to find a \((2,\ell)\)-co-clustering avoiding the pair \((\alpha,\gamma)\) and, additionally, either \((\alpha,\beta)\) or \((\beta,\gamma)\). Finding a \((2,\ell)\)-co-clustering avoiding \((\alpha,\gamma)\):  
In this case, we substitute \(\alpha:=0\), \(\beta:=1\) and \(\gamma:=2\). We describe an algorithm for finding a \((2,\ell)\)-co-clustering of cost one (avoiding \((0,2)\)). We assume that there is no \((2,\ell-1)\)-co-clustering of cost one (iterating over all values from two to \(\ell\)). Consider a \((2,\ell)\)-co-clustering \((\mathcal{I},\mathcal{J}=\{J_{1},\ldots,J_{\ell}\})\) of cost one, that is for all \((r,s)\in[2]\times[\ell]\), it holds \(\mathcal{A}_{rs}\subseteq\{0,1\}\) or \(\mathcal{A}_{rs}\subseteq\{1,2\}\). For \(s\
eq t\in[\ell]\), let \((\mathcal{I},\mathcal{J}_{st}:=\mathcal{J}\setminus\{J_{s},I_{t}\}\cup\{J_{s} \cup I_{t}\})\) denote the \((2,\ell-1)\)-co-clustering where the column blocks \(J_{s}\) and \(J_{t}\) are merged. By assumption, for all \(s\
eq t\in[\ell]\), it holds that \(\operatorname{cost}_{\infty}(\mathcal{I},\mathcal{J}_{st})>1\), since otherwise, we have found a \((2,\ell-1)\)-co-clustering of cost one.