# Shelved-Retrieved Method for Weakly Balanced Constrained Clustering Problems
## 3 Methodology
### Shelved-Retrieved Method
17: Assign \(\mathbf{x}_{j}\) to \(C_{i}\) and \(K\), and update \(R\) based on \(A_{\mathbf{x}_{j}}\). 18:endfor
19:endif
20:endwhile
```  
**Algorithm 1** Clustering by power diagrams based on connectivity  
The shelved-retrieved method uses Algorithm 2 to cluster the points. In each iteration, denoted by \(p\), parameters \(\alpha_{i}\) and \(e_{i}:=\omega(C_{i})-\kappa_{i}\) are represented by \(\alpha_{i}^{p}\) and \(e_{i}^{p}\), respectively. \(\operatorname*{sgn}(\cdot)\) denotes the sign function. The sites can be updated by the Lloyd algorithm [25] in the clustering. \[\alpha_{i}^{p+1}= \begin{cases}\alpha_{i}^{p}-0.1\text{sgn}(e_{i}^{p})\min_{j=1,\dots,n,j\
eq i}d(\mathbf{s}_{i},\mathbf{s}_{j})&\text{if }p=1\\ \alpha_{i}^{p}-0.2\text{sgn}(e_{i}^{p})\min_{j=1,\dots,n,j\
eq i}d(\mathbf{s}_{i}, \mathbf{s}_{j})/n&\text{if }p\geq 2\text{ and }(\alpha_{i}^{p}-\alpha_{i}^{p-1})(e_{i}^{p}-e_{i}^{p-1})\
eq 0 \\ \alpha_{i}^{p}-\min\left\{\left|\frac{e_{i}^{p}-e_{i}^{p-1}}{e_{i}^{p}-e_{i}^{ p}}e_{i}^{p}\right|,0.2\min_{j=1,\dots,n,j\
eq i}d(\mathbf{s}_{i},\mathbf{s}_{j})/n\right\} \text{sgn}(e_{i}^{p})&\text{otherwise}\end{cases}  \tag{4}\]  
Figure 1: The assigning process of the shelved–retrieved method: The black, hollow, red, and blue points represent those that belong to clusters, have not undergone processing yet, are eligible candidates for assignment to clusters, and are temporarily unassigned to any clusters, respectively. (**a**) Initial state; (**b**) Finding the adjacent points; (**c**) Assigning points. ```
0: Domain \(X=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{m}\}\), weight set \(\Omega=\{\omega_{1},\ldots,\omega_{m}\}\), set \(K=\{\kappa_{1},\ldots,\kappa_{n}\}\), weight matrix \(A_{\omega}\), adjacent set \(A_{\mathbf{x}_{j}}\) for each point \(\mathbf{x}_{j}\), and maximum number of iterations \(M\). 0: Clustering solution \(\mathcal{C}=\{C_{1},\ldots,C_{n}\}\)
1: Initialize \(\mathbf{s}_{1},\ldots,\mathbf{s}_{n}\), \(\alpha_{1}=0,\ldots,\alpha_{n}=0\). 2:repeat
3:\(p=1\)
4:repeat
5: Obtain the clustering \(\mathcal{C}\) by the Algorithm 1. 6: Update \(\alpha_{i}^{p+1}\) by Formula (4) for each \(i\). 7:\(p\gets p+1\)
8:until\(p>M\) or \(\mathcal{C}\) satisfies the constraints on cluster weights. 9: Update \(\mathbf{s}_{1},\ldots,\mathbf{s}_{n}\) by the Lloyd algorithm. 10:until\(\mathbf{s}_{1},\ldots,\mathbf{s}_{n}\) remain the same values. ```  
**Algorithm 2** Shelved-retrieved method  
Using the aforementioned process, the shelved-retrieved method can produce a connected solution for Model (1), as stated in Lemma 2. Lemma 2: _The shelved-retrieved method can produce a feasible solution for Model (1)._  
Proof. : The shelved-retrieved method ensures that each point in a cluster is connected to the cluster site through a path, thereby resulting in connected clustering. Here, we prove that the clustering results satisfy the inequality constraints on the cluster weights. For each cluster \(C_{i}\), we can obtain point \(\mathbf{x}_{j}\) that satisfies  
\[j=\operatorname*{arg\,max}_{j:\mathbf{x}_{j}\in C_{i}}\frac{(\