Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ${\ell }_p$-Distances

Grigory Yaroslavtsev, Adithya Vadapalli

We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of $n$ input $d$-dimensional vectors under Hamming, $\e…