# Co-Clustering under the Maximum Norm+
## 3 Intractability Results
### Clustering into Consecutive Clusters  
One is tempted to assume that the hardness of the previous special cases of Co-Clustering\({}_{\sf{oo}}\) is rooted in the fact that we are allowed to choose arbitrary subsets for the corresponding row and column partitions since the problem remains hard even for a constant number of clusters and also with equal cluster sizes. Hence, in this section, we consider a restricted version of Co-Clustering\({}_{\sf{oo}}\), where the row and the column partition has to consist of consecutive blocks. Formally, for row indices  
Figure 3: Example of a Box Cover instance with seven points (**left**) and the corresponding Co-Clustering\({}_{\sf{oo}}\) matrix containing the coordinates of the points as columns (**right**). Indicated is a \((2,3)\)-co-clustering of cost two where the column blocks are colored according to the three squares (of side length two) that cover all points. \(R=\{r_{1},\ldots,r_{k-1}\}\) with \(1<r_{1}<\ldots<r_{k-1}\leq m\) and column indices \(C=\{c_{1},\ldots,c_{\ell-1}\}\) with \(1<c_{1}<\ldots<c_{\ell-1}\leq n\), the corresponding _consecutive_\((k,\ell)\)-co-clustering \((\mathcal{I}_{R},\mathcal{J}_{C})\) is defined as:  
\[\mathcal{I}_{R} :=\{\{1,\ldots,r_{1}-1\},\{r_{1},\ldots,r_{2}-1\},\ldots,\{r_{k-1 },\ldots,m\}\}\] \[\mathcal{J}_{C} :=\{\{1,\ldots,c_{1}-1\},\{c_{1},\ldots,c_{2}-1\},\ldots,\{c_{ \ell-1},\ldots,n\}\}\]  
The Consecutive Co-Clustering\({}_{\infty}\) problem now is to find a consecutive \((k,\ell)\)-co-clustering of a given input matrix with a given cost. Again, also this restriction is not sufficient to overcome the inherent intractability of co-clustering, that is we prove it to be NP-hard. Similarly to Section 3.2, we encounter a close relation of consecutive co-clustering to a geometric problem, namely to find an optimal discretization of the plane; a preprocessing problem with applications in data mining [5; 6; 7]. The NP-hard Optimal Discretization problem [6] is the following: Given a set \(S=B\cup W\) of points in the plane, where each point is either colored black (\(B\)) or white (\(W\)), and integers \(k,\ell\in\mathbb{N}\), decide whether there is a consistent set of \(k\) horizontal and \(\ell\) vertical (axis-parallel) lines. That is, the vertical and horizontal lines partition the plane into rectangular regions, such that no region contains two points of different colors (see Figure 4 for an example). Here, a vertical (horizontal) line is a simple number denoting its \(x\)- (\(y\)-) coordinate. **Theorem 3**. : Consecutive Co-Clustering\({}_{\infty}\) _is NP-hard for \(\Sigma=\{0,1,2\}\)._  
Proof. : We give a polynomial-time reduction from Optimal Discretization. Let \((S,k,\ell)\) be an Optimal Discretization instance; let \(X:=\{x_{1}^{*},\ldots,x_{n}^{*}\}\) be the set of different \(x\)-coordinates; and let \(Y:=\{y_{1}^{*},\ldots,y_{m}^{*}\}\) be the set of different \(y\)-coordinates of the points in \(S\). Note that \(n\) and \(m\) can be smaller than \(|S|\), since two points can have the same \(x\)- or \(y\)-coordinate. Furthermore, assume that \(x_{1}^{*}<\ldots<x_{n}^{*}\) and \(y_{1}^{*}<\ldots<y_{m}^{*}\). We now define the Consecutive Co-Clustering\({}_{\infty}\) instance \((\mathcal{A},k+1,\ell+1,c)\) as follows: The matrix \(\mathcal{A}\in\{0,1,2\}^{m\times n}\) has columns labeled with \(x_{1}^{*},\ldots,x_{n}^{*}\) and rows labeled with \(y_{1}^{*},\ldots,y_{m}^{*}\). For \((x,y)\in X\times Y\), the entry \(a_{xy}\) is defined as zero if \((x,y)\in W\), two if \((x,y)\in B\) and otherwise one. The cost is set to \(c:=1\). Clearly, this instance can be constructed in polynomial time. To verify the correctness of the reduction, assume first that \(I\) is a yes-instance, that is there is a set \(H=\{x_{1},\ldots,x_{k}\}\) of \(k\) horizontal lines and a set \(V=\{y_{1},\ldots,y_{\ell}\}\) of \(\ell\) vertical lines partitioning the plane consistently.