TY - GEN
T1 - Improved Approximation Algorithm for the Distributed Lower-Bounded k-Center Problem
AU - Liang, Ting
AU - Feng, Qilong
AU - Wu, Xiaoliang
AU - Xu, Jinhui
AU - Wang, Jianxin
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
PY - 2024
Y1 - 2024
N2 - Clustering large data is a fundamental task with widespread applications. The distributed computation methods have received greatly attention in recent years due to the increasing size of data. In this paper, we consider a variant of the widely used k-center problem, i.e., the lower-bounded k-center problem, and study the lower-bounded k-center problem in the Massively Parallel Computation (MPC) model. The lower-bounded k-center problem takes as input a set C of points in a metric space, the desired number k of centers, and a lower bound L. The goal is to partition the set C into at most k clusters such that the number of points in each cluster is at least L, and the k-center clustering objective is minimized. The current best result for the above problem in the MPC model is 16-approximation algorithm with 4 rounds. In this paper, we obtain a 2-round (7+ϵ)-approximation algorithm for this problem in the MPC model.
AB - Clustering large data is a fundamental task with widespread applications. The distributed computation methods have received greatly attention in recent years due to the increasing size of data. In this paper, we consider a variant of the widely used k-center problem, i.e., the lower-bounded k-center problem, and study the lower-bounded k-center problem in the Massively Parallel Computation (MPC) model. The lower-bounded k-center problem takes as input a set C of points in a metric space, the desired number k of centers, and a lower bound L. The goal is to partition the set C into at most k clusters such that the number of points in each cluster is at least L, and the k-center clustering objective is minimized. The current best result for the above problem in the MPC model is 16-approximation algorithm with 4 rounds. In this paper, we obtain a 2-round (7+ϵ)-approximation algorithm for this problem in the MPC model.
KW - approximation algorithm
KW - k-center
KW - lower-bounded k-center
UR - https://www.scopus.com/pages/publications/85193241946
U2 - 10.1007/978-981-97-2340-9_26
DO - 10.1007/978-981-97-2340-9_26
M3 - Conference contribution
AN - SCOPUS:85193241946
SN - 9789819723393
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 309
EP - 319
BT - Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Proceedings
A2 - Chen, Xujin
A2 - Li, Bo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th Annual Conference on Theory and Applications of Models of Computation, TAMC 2024
Y2 - 13 May 2024 through 15 May 2024
ER -