# Shelved-Retrieved Method for Weakly Balanced Constrained Clustering Problems
## 1 Introduction  
Clustering is a foundational task for applications in real-world scenarios [1; 2] including resource allocation [3] and site selection [4]. It typically involves partitioning a set of points into several subsets, referred to as clusters, such that the points in the same cluster are similar, while those in different clusters are dissimilar. In transportation and partitioning, it is not sufficient to merely partition points according to similarity for clustering [5; 6]. Owing to limited resources and the need for efficient transport, clusters must additionally meet other specific requirements, among which we are most concerned about weight constraints and cluster connectivity [7; 8; 9; 10; 11; 12; 13; 14]. Weight constraints originate from a prominent and challenging concern regarding resource limitations in transportation and partitioning scenarios. The weight of a point is usually associated with some problem-specified quantity, such as the size, area, or volume of the corresponding object. The cumulative weight of points within a cluster, also referred to as the cluster weight, is required to remain within a predetermined capacity range. For example, constraints of this kind are raised when the number of deliveries within the service area of an express service station must not exceed its designated capacity limits. This can be achieved by limiting the cluster weights within specific intervals. Cluster connectivity is another type of constraint often encountered in practice. In scenarios such as farmland consolidation, some points in the area may be separated by barriers [12; 13]. A route connecting two separate points is required to bypass the barriers, which can cost significantly more than connecting two points that are at the same distancebut are not separated by any barrier. As such, transporting between these points directly may be impossible or unreasonable, thereby resulting in their disconnection. Generalized from disconnection between point pairs, the cluster connectivity constraint requests that a cluster cannot be split into two subsets such that any point pair between the subsets is disconnected. The inconsistency between connectivity and geometric proximity makes the cluster connectivity constraint a great challenge for the design of an algorithm. In this paper, the similarity between points is assessed via a cost kernel, a commonly used technique that generalizes the classical Euclidean distance-based similarity. Similar to the partitioning clustering, the results should reach the goal that the costs within clusters are lower enough and the costs between the clusters are high enough according to the cost kernel. The clustering problem with cost kernel under the constraints on cluster weights and connectivity is formally known as the _weakly balanced constrained clustering_ (WBCC) problem. The clustering problem with a cost kernel is easy to solve by traditional clustering methods, but it is challenging to handle constraints on cluster weights and connectivity. Traditional clustering methods partition points into clusters using similarity metrics and optimize the compactness of clusters. The cluster weights are not relative to the reduction in the objective functions in clustering; thus, they cannot be adjusted through the optimization of the objective function. In addition, the cluster connectivity fails to be quantified by the cost kernel. Therefore, it is particularly challenging to address these constraints in clustering. To handle the constraints on cluster weights, previous methods used power diagrams for clustering point sets [5; 8; 10; 12; 13]. They partitioned points \(\mathbf{x}\in X\) into clusters \(C_{i}\) with associated sites \(\mathbf{s}_{i}\) using an additively weighted distance, i.e.,  
\[C_{i}=\{\mathbf{x}:\|\mathbf{x}-\mathbf{s}_{i}\|_{2}-\alpha_{i}\leq\|\mathbf{x}-\mathbf{s}_{j}\|_ {2}-\alpha_{j}\}.\]  
These methods obtain the cluster weights satisfying the constraints by the optimization of parameters \(\alpha_{i}\).