# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Reduction to CNF-SAT Solving  
In this section, we describe two approaches to solve Co-Clustering\({}_{\infty}\) via CNF-SAT. The first approach is based on a straightforward reduction of a Co-Clustering\({}_{\infty}\) instance to one CNF-SAT instance with clauses of size at least four. Note that this does not yield any theoretical improvements in general. Hence, we develop a second approach, which requires solving \(O(|\Sigma|^{k\ell})\) many CNF-SAT instances with clauses of size at most \(\max\{k,\ell,2\}\). The theoretical advantage of this approach is that if \(k\) and \(\ell\) are constants, then there are only polynomially many CNF-SAT instances to solve. Moreover, the formulas contain smaller clauses (for \(k\leq\ell\leq 2\), we even obtain polynomial-time solvable 2-SAT instances). While the second approach leads to (theoretically) tractable special cases, it is not clear that it also performs better in practice. This is why we conducted some experiments for empirical comparison of the two approaches (in fact, it turns out that the straightforward approach allows one to solve larger instances). In the following, we describe the reductions in detail and briefly discuss the experimental results. We start with the straightforward polynomial-time reduction from Co-Clustering\({}_{\infty}\) to CNF-SAT. We simply introduce a variable \(x_{i,r}\) (\(y_{j,s}\)) for each pair of row index \(i\in[m]\) and row block index \(r\in[k]\) (respectively, column index \(j\in[n]\) and column block index \(s\in[\ell]\)) denoting whether the respective row (column) may be put into the respective row (column) block. For each row \(i\), we enforce that it is put into at least one row block with the clause \((x_{i,1}\vee\ldots\lor x_{i,k})\) (analogously for the columns). We encode the cost constraints by introducing \(k\ell\) clauses \((\
eg x_{i,r}\vee\
eg x_{i^{\prime},r}\vee\
eg y_{js}\vee\
eg y_{j^{\prime},s})\), \((r,s)\in[k]\times[\ell]\) for each pair of entries \(a_{ij},a_{i^{\prime}j}\in\mathcal{A}\) with \(|a_{ij}-a_{i^{\prime}j^{\prime}}|>c\). These clauses simply ensure that \(a_{ij}\) and \(a_{i^{\prime}j^{\prime}}\) are not put into the same cluster. Note that this reduction yields a CNF-SAT instance with \(km+\ell n\) variables and \(O((mn)^{2}k\ell)\) clauses of size up to \(\max\{k,\ell,4\}\). Based on experiments (using the PicoSAT Solver of Biere [17]), which we conducted on randomly generated synthetic data (of size up to \(m=n=1000\)), as well as on a real-world dataset (_animals with attributes_ dataset [18] with \(m=50\) and \(n=85\)), we found that we can solve instances up to \(k=\ell=11\) using the above CNF-SAT approach. In our experiments, we first computed an upper and a lower bound on the optimal cost value \(c\) and then created the CNF-SAT instances for decreasing values for \(c\), starting from the upper bound. The upper and the lower bound have been obtained as follows: Given a \((k,\ell)\)-Co-Clustering\({}_{\infty}\) instance on \(\mathcal{A}\), solve \((k,n)\)-Co-Clustering\({}_{\infty}\) and \((m,\ell)\)-Co-Clustering\({}_{\infty}\) separately for input matrix \(\mathcal{A}\). Let \((\mathcal{I}_{1},\mathcal{J}_{1})\) and \((\mathcal{I}_{2},\mathcal{J}_{2})\) denote the \((k,n)\)- and \((m,\ell)\)-co-clustering, respectively, and let their costs be \(c_{1}:=\text{cost}(\mathcal{I}_{1},\mathcal{J}_{1})\) and \(c_{2}:=\text{cost}(\mathcal{I}_{2},\mathcal{J}_{2})\). We take \(\max\{c_{1},c_{2}\}\) as a lower bound and \(c_{1}+c_{2}\) as an upper bound on the optimal cost value for an optimal \((k,\ell)\)-co-clustering of \(\mathcal{A}\). It is straightforward to argue the correctness of the lower bound, and we next show that \(c_{1}+c_{2}\) is an upper bound. Consider any pair \((i,j),(i^{\prime},j^{\prime})\in[m]\times[n]\), such that \(i\) and \(i^{\prime}\) are in the same row block of \(\mathcal{I}_{1}\), and \(j\) and \(j^{\prime}\) are in the same column block of \(\mathcal{J}_{2}\) (that is, \(a_{ij}\) and \(a_{j^{\prime}}\) are in the same cluster).