# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Reduction to CNF-SAT Solving
Then, it holds \(|a_{ij}-a_{i^{\prime}j^{\prime}}|\leq|a_{ij}-a_{i^{\prime}j}|+|a_{ij}-a_{i^{ \prime}j^{\prime}}|\leq c_{1}+c_{2}\). Hence, just taking the row partitions from \((\mathcal{I}_{1},\mathcal{J}_{1})\) and the column partitions from \((\mathcal{I}_{2},\mathcal{J}_{2})\) gives a combined \((k,\ell)\)-co-clustering of cost at most \(c_{1}+c_{2}\). From a theoretical perspective, the above naive approach of solving Co-Clustering\({}_{\infty}\) via CNF-SAT does not yield any improvement in terms of polynomial-time solvability. Therefore, we now describe a different approach, which leads to some polynomial-time solvable special cases. To this end, we introduce the concept of _cluster boundaries_, which are basically lower and upper bounds for the values in a cluster of a co-clustering. Formally, given two integers \(k,\ell\), an alphabet \(\Sigma\) and a cost \(c\), we define a cluster boundary to be a matrix \(\mathcal{U}=(u_{rs})\in\Sigma^{k\times\ell}\). We say that a \((k,\ell)\)-co-clustering of \(\mathcal{A}\)_satisfies_ a cluster boundary \(\mathcal{U}\) if \(\mathcal{A}_{rs}\subseteq[u_{rs},u_{rs}+c]\) for all \((r,s)\in[k]\times[\ell]\). It can easily be seen that a given \((k,\ell)\)-co-clustering has cost at most \(c\) if and only if it satisfies at least one cluster boundary \((u_{rs})\), namely the one with \(u_{rs}=\min\mathcal{A}_{rs}\). The following \"subtask\" of Co-Clustering\({}_{\infty}\) can be reduced to a certain CNF-SAT instance: Given a cluster boundary \(\mathcal{U}\) and a Co-Clustering\({}_{\infty}\) instance \(I\), find a co-clustering for \(I\) that satisfies \(\mathcal{U}\). The polynomial-time reduction provided by the following lemma can be used to obtain exact Co-Clustering\({}_{\infty}\) solutions with the help of SAT solvers, and we use it in our subsequent algorithms. **Lemma 1**. : _Given a Co-Clustering\({}_{\infty}\)-instance \((\mathcal{A},k,\ell,c)\) and a cluster boundary \(\mathcal{U}\), one can construct in polynomial time a CNF-SAT instance \(\phi\) with at most \(\max\{k,\ell,2\}\) variables per clause, such that \(\phi\) is satisfiable if and only if there is a \((k,\ell)\)-co-clustering of \(\mathcal{A}\), which satisfies \(\mathcal{U}\)._  
Proof. : Given an instance \((\mathcal{A},k,l,c)\) of Co-Clustering\({}_{\infty}\) and a cluster boundary \(\mathcal{U}=(u_{rs})\in\Sigma^{k\times\ell}\), we define the following Boolean variables: For each \((i,r)\in[m]\times[k]\), the variable \(x_{i,r}\) represents the expression \"row \(i\) could be put into row block \(I_{r}\)\". Similarly, for each \((j,s)\in[n]\times[\ell]\), the variable \(y_{j,s}\) represents that \"column \(j\) could be put into column block \(J_{s}\)\". We now define a Boolean CNF formula \(\phi_{\mathcal{A}\mathcal{U}}\) containing the following clauses: a clause \(R_{i}:=(x_{i,1}\lor x_{i,2}\vee\ldots\lor x_{i,k})\) for each row \(i\in[m]\) and a clause \(C_{j}:=(y_{j,1}\lor y_{j,2}\vee\ldots\lor y_{j,\ell})\) for each column \(j\in[n]\). Additionally, for each \((i,j)\in[m]\times[n]\) and each \((r,s)\in[k]\times[\ell]\), such that element \(a_{ij}\) does not fit into the cluster boundary at coordinate \((r,s)\), that is \(a_{ij}\
otin[u_{rs},u_{rs}+c]\), there is a clause \(B_{ijrs}:=(\
eg x_{i,r}\vee\
eg y_{j,s})\). Note that the clauses \(R_{i}\) and \(C_{j}\) ensure that row \(i\) and column \(j\) are put into some row and some column block, respectively. The clause \(B_{ijrs}\) expresses that it is impossible to have both row \(i\) in block \(I_{r}\) and column \(j\) in block \(J_{s}\) if \(a_{ij}\) does not satisfy \(u_{rs}\leq a_{ij}\leq u_{rs}+c\). Clearly, \(\phi_{\mathcal{A}\mathcal{U}}\) is satisfiable if and only if there exists a \((k,\ell)\)-co-clustering of \(\mathcal{A}\) satisfying the cluster boundary \(\mathcal{U}\). Note that \(\phi_{\mathcal{A}\mathcal{U}}\) consists of \(km+\ell n\) variables and \(O(mnk\ell)\) clauses.