2023/09/08 by Aghamolaei, Sepideh, Ghodsi, Mohammad
#Computational Geometry (cs.CG) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2309.04327
In a metric space, a set of point sets of roughly the same size and an integer k≥ 1 are given as the input and the goal of data-distributed k-center is to find a subset of size k of the input points as the set of centers to minimize the maximum distance from the input points to their closest centers. Metric k-center is known to be NP-hard which carries to the data-distributed setting. We give a 2-approximation algorithm of k-center for sublinear k in the data-distributed setting, which is tight. This algorithm works in several models, including the massively parallel computation model (MPC).