## 2 Methods
### Greedy Agglomerative Procedures  
The agglomerative approach to solving the p-median problem is often successful [70]. To solve the p-median problem in a continuous space, the authors of [60] use genetic algorithms with various crossover operators based on greedy agglomerative procedures. [PERSON], [PERSON], and [PERSON] in [70] presented a genetic algorithm for facility location problems, where evolution is facilitated by a greedy agglomerative heuristic procedure. A genetic  
Figure 1: Comparative results of the search in SWAP\(r\) neighborhoods. Dependence of the result (1) on \(r\): (**a**) BIRCH3 dataset, search for 300 centers, 100,000 data vectors, time limitation 10 s; (**b,c**) IHEPC dataset, search for 100 and 300 centers, respectively, 2,075,259 data vectors, time limitation 300 s; (**d**) Mopsi-Finland dataset, search for 30 centers, 13,467 data vectors, time limitation 5 s.  
algorithm with a faster greedy heuristic procedure for clustering and location problems was also proposed in [71]. Greedy agglomerative procedures can be used as independent algorithms or embedded in VNS or evolutionary algorithms [52; 96]. Such procedures can be described as follows in Algorithm 2:  
```
Require: Set of initial centroids \(S=\{X1,\ldots,X_{K}\}\), \(|S|=K>k\), required final number of centroids \(k\). Improve \(S\) with the two-step local search algorithm if possible; while\(|S|>k\)do for\(i=\overline{1,|S|}\)do \(F_{i}\gets SSE(S\backslash\{X_{i}\})\); endfor Select a subset \(S^{\prime}\subset S\) of to remove centroids with the minimum values of the corresponding variables \(F_{i^{\prime}}\); // By default, \(r_{\textit{tremovave}}=1\);  Improve this new solution \(S\leftarrow(S\backslash S^{\prime})\); with the two-step local search algorithm; endwhile. ```  
**Algorithm 2** BasicAggl (\(S\))  
To improve the performance of such a procedure, the number of simultaneously eliminated centers can be calculated as \(r_{\textit{tremovave}}=\max\Big{\{}1,\lceil(|S|-p)\cdot r_{\textit{coef}} \rceil\Big{\}}\). In [52; 97], the authors used the elimination coefficient value \(r_{\textit{coef}}=0.2\). This means that at each iteration, up to 20% of the excessive centers are eliminated, and such values are proved to make the algorithm faster. The agglomerative procedure for obtaining an AGGL\({}_{\tau}\) neighborhood can be defined as follows in Algorithm 3:  
```
Require: Two sets of centers \(S\), \(S_{2}\), \(|S|=|S_{2}|=p\), the number of centers \(r\) of the solution \(S_{2}\) which are used to obtain the resulting solution, \(r\in\{\overline{1,p}\}\). for\(i=\overline{1,n_{\textit{repeats}}}\)do 1. Select a subset \(S^{\prime}\subset S_{2}:\ |S^{\prime}|=r\); 2. \(S^{\prime}\leftarrow\textit{BasicGreedy}(S\cup\ S^{\prime})\); 3. if\(F(S^{\prime})<F(S)\)then \(S\gets S^{\prime}\)  end if; endfor return\(S\). ```  
**Algorithm 3** AGGLr (\(S\), \(S_{2}\))  
Such procedures use various values of \(r\in\{\overline{1,p}\}\), and \(n_{\textit{repeats}}\) depends on \(r\). \(n_{\textit{repeats}}=\max\{1,[p/r]\}\). If the solution \(S_{2}\) is fixed, then all possible results of applying the AGGL\({}_{\tau}\) (\(S\), \(S_{2}\)) procedure form a neighborhood of the solution \(S\), and \(S_{2}\) as well as \(r\) are parameters of such a neighborhood. If \(S_{2}\) is a randomly chosen locally optimal solution obtained by \(\textit{ALA}\) (\(S_{2^{\prime}}\)) procedure applied to a randomly chosen subset \(S^{\prime}_{2}\subset\{A_{1},\ldots,A_{N}\}\), \(|S_{2^{\prime}}|=p\), then we deal with a randomized neighborhood. Let us denote such a neighborhood by AGGL\({}_{\tau}\) (\(S\)). Our experiments demonstrate that the obtained result of the local search in AGGL\({}_{\tau}\) neighborhoods strongly depends on \(r\) (see Figure 2). As mentioned above, the greedy agglomerative procedure AGGL\({}_{\tau}\) can be used as the crossover operator of the genetic algorithms. Algorithms proposed in [52; 71] use such procedures with \(r=1\) and \(r=p\) for solving the k-means and p-median problems.