# Shelved-Retrieved Method for Weakly Balanced Constrained Clustering Problems
## 3 Methodology
### Shelved-Retrieved Method  
To solve the WBCC model (1), the shelved-retrieved method embeds adjacent relationships into the construction of the power diagrams. This integration is essential for the generation of connected clusters. It is crucial that clustering results remain connected throughout the process. Then, each point should be adjacent to at least one other point within the same cluster during the clustering procedure. In other words, they can only be assigned to clusters to which adjacent points belong. Here, we specify the assignment process for the shelved-retrieved method. We take cluster one as an example. The shelved-retrieved method randomly selects a point from the dataset to serve as the initial site for cluster one. This selected point is assigned to cluster one and colored black in Figure 0(a). Further, the adjacent hollow points of black points \(\mathbf{s}_{1},\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3},\mathbf{x}_{4},\mathbf{x}_{5}\) are identified and colored red in Figure 0(b). According to parameters \(\alpha_{i},\ i=1,\ldots,n\), the shelved-retrieved method estimates whether \(f(\mathbf{x}_{j},\mathbf{s}_{1})^{2}-\alpha_{1}\) is smaller than \(f(\mathbf{x}_{j},\mathbf{s}_{1})^{2}-\alpha_{i},i=2,\ldots,n\) at each point \(\mathbf{x}_{j}\). Assuming that \(f(\mathbf{x}_{1},\mathbf{s}_{1})^{2}-\alpha_{1},\ f(\mathbf{x}_{2},\mathbf{s}_{1})^{2}-\alpha_{1}\), \(f(\mathbf{x}_{5},\mathbf{s}_{1})^{2}-\alpha_{1}\) are the smallest and \(f(\mathbf{x}_{3},\mathbf{s}_{1})^{2}-\alpha_{1}\), \(f(\mathbf{x}_{4},\mathbf{s}_{1})^{2}-\alpha_{1}\) are not, the shelved-retrieved method assigns points \(\mathbf{x}_{1},\ \mathbf{x}_{2},\ \mathbf{x}_{5}\) to cluster one, and we color them black in Figure 0(c). Points \(\mathbf{x}_{3}\) and \(\mathbf{x}_{4}\) are colored blue. The shelved-retrieved method repeats the aforementioned operations until no additional adjacent hollow points are identified. Several blue and hollow points might not have been assigned to any cluster. These blue points are adjacent to other points within the same cluster during the clustering process. They are assigned to the clusters to which their adjacent points belong. Using blue points \(\mathbf{x}_{j}\), the shelved-retrieved method identifies a set of clusters denoted by \(\mathcal{A}=\{C_{i}:\mathbf{x}_{k}\in C_{i},\ \mathbf{x}_{k}\) is a black point adjacent to \(\mathbf{x}_{j}\}\). The minimum \(d(\mathbf{x}_{j},\mathbf{s}_{i^{\prime}})^{2}-\alpha_{i}\), is within the set \(\{f(\mathbf{x}_{j},\mathbf{s}_{i})^{2}-\alpha_{i}:\mathbf{s}_{i}\in C_{i},C_{i}\in\mathcal{ A}\}\), while point \(\mathbf{x}_{j}\) is assigned to cluster \(i^{*}\). The shelved-retrieved method repeats the process until all the points are turned black, as shown in Figure 1. Here, the aforementioned mechanism for clustering points with fixed parameters is concluded in Algorithm 1. ```
0: Domain \(X=\{\mathbf{x}_{1},\dots,\mathbf{x}_{m}\}\), sites \(\mathbf{s}_{1},\dots,\mathbf{s}_{n}\), parameters \(\alpha_{1},\dots,\alpha_{n}\), adjacent set \(A_{\mathbf{x}_{j}},j=1,\dots,m\)
0: Clustering solution \(\mathcal{C}=\{C_{1},\dots,C_{n}\}\)
1: Initialize blue point set \(B=\emptyset\), black point set \(K=\emptyset\), red point set \(R=\emptyset\), cluster \(C_{i}=\{\mathbf{s}_{i}\}\), \(i=1,\dots,n\). 2: Update \(R\) based on \(A_{\mathbf{s}_{i}}\). 3:while\(R\
eq\emptyset\)do
4:for\(\mathbf{x}_{j}\in R\)do
5:for\(i=1,\dots,n\)do
6:if\(i=\operatorname*{arg\,min}_{i^{\prime}=1,\dots,n}f(\mathbf{x}_{j},\mathbf{s}_{i^{ \prime}})^{2}-\alpha_{i^{\prime}}\)then
7: Assign \(\mathbf{x}_{j}\) to \(C_{i}\) and \(K\), and update \(R\) based on \(A_{\mathbf{x}_{j}}\). 8:endif
9:endfor
10:if\(\mathbf{x}_{j}\
otin K\)then
11: Assign \(\mathbf{x}_{j}\) to \(B\). 12:endif
13:endfor
14:if\(R=\emptyset\) and \(K\
eq X\)then
15:for\(\mathbf{x}_{j}\in B\)do
16: Calculate \(i=\operatorname*{arg\,min}_{i^{\prime}\in\{C_{i}C_{i}^{\prime}K\cap\Lambda_{ \mathbf{x}_{j}}\
eq\emptyset\}}f(\mathbf{x}_{j},\mathbf{s}_{i^{\prime}})^{2}-\alpha_{i^{ \prime}}\).