## 2 Methods
### CUDA Implementation of Greedy Agglomerative Procedures
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Algorithm or Neighborhood**} & \multicolumn{4}{c}{**Achieved Objective Function Values (1) Summarized after 30 Runs**} \\ \cline{2-5}  & **Min (Record)** & **Max (Worst)** & **Average** & **Median** & **Std. Dev** \\ \hline Lloyd (multistart) & \(1.14205\times 10^{8}\) & \(1.16737\times 10^{8}\) & \(1.15594\times 10^{8}\) & \(1.15666\times 10^{8}\) & \(6.33573\times 10^{5}\) \\ j-means (SWAP\({}_{1}\) + Lloyd) & \(1.13500\times 10^{8}\) & \(1.17631\times 10^{8}\) & \(1.15035\times 10^{8}\) & \(1.14954\times 10^{8}\) & \(9.38353\times 10^{5}\) \\ AGGL\({}_{1}\) & \(1.13121\times 10^{8}\) & \(1.15265\times 10^{8}\) & \(1.14219\times 10^{8}\) & \(1.14035\times 10^{8}\) & \(6.23645\times 10^{5}\) \\ AGGL\({}_{2}\) & \(1.12430\times 10^{8}\) & \(1.12572\times 10^{8}\) & \(1.12475\times 10^{8}\) & \(1.12464\times 10^{8}\) & \(3.76180\times 10^{4}\) \\ AGGL\({}_{3}\) & \(1.12426\times 10^{8}\) & \(1.12548\times 10^{8}\) & \(1.12465\times 10^{8}\) & \(1.12457\times 10^{8}\) & \(2.92460\times 10^{4}\) \\ AGGL\({}_{5}\) & \(1.124465\times 10^{8}\) & \(1.12525\times 10^{8}\) & \(1.12487\times 10^{8}\) & \(1.12483\times 10^{8}\) & \(3.00588\times 10^{4}\) \\ AGGL\({}_{7}\) & \(1.12437\times 10^{8}\) & \(1.12591\times 10^{8}\) & \(1.12481\times 10^{8}\) & \(1.12478\times 10^{8}\) & \(3.26658\times 10^{4}\) \\ AGGL\({}_{10}\) & \(1.12462\times 10^{8}\) & \(1.12558\times 10^{8}\) & \(1.12500\times 10^{8}\) & \(1.12500\times 10^{8}\) & \(2.68212\times 10^{4}\) \\ AGGL\({}_{15}\) & \(1.12462\times 10^{8}\) & \(1.12579\times 10^{8}\) & \(1.12526\times 10^{8}\) & \(1.12528\times 10^{8}\) & \(2.83854\times 10^{4}\) \\ AGGL\({}_{20}\) & \(1.12461\times 10^{8}\) & \(1.12590\times 10^{8}\) & \(1.12535\times 10^{8}\) & \(1.12538\times 10^{8}\) & \(3.27419\times 10^{4}\) \\ AGGL\({}_{25}\) & \(1.12472\times 10^{8}\) & \(1.12632\times 10^{8}\) & \(1.12541\times 10^{8}\) & \(1.12543\times 10^{8}\) & \(3.4545\times 10^{4}\) \\ AGGL\({}_{30}\) & \(1.12523\times 10^{8}\) & \(1.12662\times 10^{8}\) & \(1.12572\times 10^{8}\) & \(1.12566\times 10^{8}\) & \(3.55121\times 10^{4}\) \\ AGGL\({}_{50}\) & \(1.12541\times 10^{8}\) & \(1.12848\times 10^{8}\) & \(1.12666\times 10^{8}\) & \(1.12651\times 10^{8}\) & \(7.48936\times 10^{4}\) \\ GH-VNS1 & \(1.12419\times 10^{8}\) & \(1.12796\times 10^{8}\) & \(1.12467\times 10^{8}\) & \(1.12446\times 10^{8}\) & \(7.47785\times 10^{4}\) \\ GH-VNS2 & \(1.12472\times 10^{8}\) & \(1.12610\times 10^{8}\) & \(1.12525\times 10^{8}\) & \(1.12519\times 10^{8}\) & \(3.37221\times 10^{4}\) \\ GH-VNS3 & \(1.12531\times 10^{8}\) & \(1.12696\times 10^{8}\) & \(1.12712\times 10^{8}\) & \(1.12708\times 10^{8}\) & \(9.60927\times 10^{4}\) \\ SWAP\({}_{1}\) (the best of SWAP) & \(1.13142\times 10^{8}\) & \(1.16627\times 10^{8}\) & \(1.14430\times 10^{8}\) & \(1.14412\times 10^{8}\) & \(8.48529\times 10^{5}\) \\ GA-1 POINT & \(1.14271\times 10^{8}\) & \(1.16790\times 10^{8}\) & \(1.15443\times 10^{8}\) & \(1.15343\times 10^{8}\) & \(7.16204\times 10^{5}\) \\ GA-UNIFORM & \(1.13119\times 10^{8}\) & \(1.15805\times 10^{8}\) & \(1.14384\times 10^{8}\) & \(1.14405\times 10^{8}\) & \(6.75227\times 10^{5}\) \\ Aggl-EA & \(1.12476\times 10^{8}\) & \(1.15978\times 10^{8}\) & \(1.14049\times 10^{8}\) & \(1.13985\times 10^{8}\) & \(1.05017\times 10^{6}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparative results for S1 dataset. 5000 data vectors in \(\mathbb{R}^{2}\), \(p=50\) centers, time limitation 1 s.