The $k$-center problem is a fundamental optimization problem with numerous
applications in machine learning, data analysis, data mining, and communication
networks. The $k$-center problem has been extensively studied in the classical
sequential setting for several decades, and more recently there have been some
efforts in understanding the problem in parallel computing, on the Massively
Parallel Computation (MPC) model. For now, we have a good understanding of
$k$-center in the case where each local MPC machine has sufficient local memory
to store some representatives from each cluster, that is, when one has
$\Omega(k)$ local memory per machine. While this setting covers the case of
small values of $k$, for a large number of clusters these algorithms require
undesirably large local memory, making them poorly scalable. The case of large
$k$ has been considered only recently for the fully scalable low-local-memory
MPC model for the Euclidean instances of the $k$-center problem. Tuttavia, the
earlier works have been considering only the constant dimensional Euclidean
space, required a super-constant number of rounds, and produced only
$k(1+o(1))$ centers whose cost is a super-constant approximation of $k$-center.
In this work, we significantly improve upon the earlier results for the
$k$-center problem for the fully scalable low-local-memory MPC model. In the
low dimensional Euclidean case in $\mathbb{R}^d$, we present the first
constant-round fully scalable MPC algorithm for
$(2+\varepsilon)$-approximation. We push the ratio further to $(1 +
\varepsilon)$-approximation albeit using slightly more $(1 + \varepsilon)k$
centers. All these results naturally extends to slightly super-constant values
of $d$. In the high-dimensional regime, we provide the first fully scalable MPC
algorithm that in a constant number of rounds achieves an $O(\log n/ \log \log
n)$-approximation for $k$-center.

Questo articolo esplora i giri e le loro implicazioni.

Scarica PDF: