## 2 Methods
### CUDA Implementation of Greedy Agglomerative Procedures
2,075,259 data vectors in \(\mathbb{R}^{7}\), k = 300 clusters, time limitation 5 min s & & \\ j-means & \(44,074.6445\) & \(47,562.4922\) & \(45,375.1657\) & \(44,608.1953\) & \(1505.4071\) \\ Aggl-EA\(\leftrightarrow\)\(\Leftrightarrow\) & \(41,795.5078\) & \(65,057.9375\) & \(51,888.0642\) & \(42,525.5000\) & \(12,122.2332\) \\  & Mopsi-Finland dataset.13,467 data vectors in \(\mathbb{R}^{2}\), k = 300 clusters, time limitation 5 s & & \\ AGGL\({}_{7}\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(3.35641\) \\ Aggl-EA\(\leftrightarrow\)\(\Leftrightarrow\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(1.03013\times 10^{7}\) & \(2.42022\) \\  & Mopsi-Finland dataset. 13,467 data vectors in \(\mathbb{R}^{2}\), k = 100 clusters, time limitation 5 s & & \\ AGGL\({}_{25}\) & \(3.64354\times 10^{6}\) & \(3.66605\times 10^{6}\) & \(3.64913\times 10^{6}\) & \(3.64784\times 10^{6}\) & \(5184.35\) \\ AGGL\({}_{30}\) & \(3.64290\times 10^{6}\) & \(3.67201\times 10^{6}\) & \(3.65106\times 10^{6}\) & \(3.64702\times 10^{6}\) & \(7780.79\) \\ Aggl-EA\(\leftrightarrow\)\(\Leftrightarrow\) & \(3.64285\times 10^{6}\) & \(3.65052\times 10^{6}\) & \(3.64473\times 10^{6}\) & \(3.64502\timesThe time limitation plays an important role: the fastest algorithms may stop their convergence after several iterations and, vice versa, the slowest algorithms may continue their slow convergence and outperform the fastest algorithms if we enlarge their time limits. However, our new algorithms demonstrate their comparative advantage within wide time intervals (see Figure 3). ## 4 Discussion

The genetic algorithms and Variable Neighborhood Search are algorithmic frameworks useful for creating efficient solvers of various problems including location problems such as p-median. The greedy agglomerative approach can be efficiently used as the crossover genetic operator [58; 70; 71; 102] as well as in the VNS [52]. However, as our experiments show (Appendix A), the correct choice of parameter \(r\) in such procedures plays the most important role and simple search algorithms with constant value of \(r\) may outperform more complex VNS algorithms if \(r\) is tuned correctly. Unlike the majority of evolutionary algorithms, the \((1+1)\)-evolutionary algorithms as well as local search algorithms focus on the successive improvement of a single intermediate solution. Successful application of various local search algorithms such as SWAP search, j-means or various VNS algorithms including to the p-median problem shows that the correct choice of a neighborhood or an algorithmic procedure for the successive improvement

Figure 3: Comparative analysis of the convergence speed. Dependence of the median result on computation time for: (**a**) Individual Household Electric Power Consumption (IHEPC) dataset, 50 centers, 2,075,259 data vectors, time limitation 300 s; (**b**) Mopsi-Joensuu dataset, search for 300 centers, 6014 data vectors, time limitation 5 s. (**c**) Mopsi-Finland dataset, search for 300 centers, 13,467 data vectors, time limitation 5 s.

of a single current solution can be a more profitable strategy for solving practical problems than operating with a large population of solutions. In this work, we have increased the efficiency of one of these procedures by adjusting its parameter. Nevertheless, adjusting the parameters of greedy agglomerative procedures can also enhance the capabilities of genetic algorithms with a greedy agglomerative crossing operator, which, in our opinion, is an urgent area of further research. In addition, similar algorithms can be developed for a wider range of problems, including k-means, k-medoid, and the problem of separating a mixture of probability distributions. Our new algorithm demands significant computational resources.