Near-Optimal Clustering in the k-machine model
Near-Optimal Clustering in the k-machine model
复制标题
k 机模型中的近最优聚类
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sriram V. Pemmaraju
中科院分区：
文献类型：
--
作者：
Sayan Bandyapadhyay;Tanmay Inamdar;Shreyas Pai;Sriram V. Pemmaraju
在许多变体中，聚类问题在运营研究和计算机科学方面有许多应用程序（例如，随着数据集的尺寸，研究人员的尺寸越来越大，在生物信息学，图像处理，社交网络分析等中的应用中，在适合大规模计算的计算模型中设计算法，例如MapReduce，Pregel和流媒体模型。 2015年）是一个简单的消息模型，用于大规模分布式图形处理。在k-机器模型中以这些问题（N/K）弹性运行的这些问题的O（1） - 因子近似算法是最佳的。获得这些问题的poly（n）近似算法的下限。 Edge加权图和简而言之，我们的主要技术贡献是表明，只能通过学习输入度量的一小部分来获得所有三个聚类问题的恒定因子近似算法。
The clustering problem, in its many variants, has numerous applications in operations research and computer science (e.g., in applications in bioinformatics, image processing, social network analysis, etc.). As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in models of computation suited for large-scale computation such as MapReduce, Pregel, and streaming models. The k-machine model (Klauck et al., SODA 2015) is a simple, message-passing model for large-scale distributed graph processing. This paper considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the p-median problem, and the p-center problem and presents O (1)-factor approximation algorithms for these problems running in Õ (n/k) rounds in the k -machine model. These algorithms are optimal upto polylogarithmic factors because this paper also shows Ω (n/k) lower bounds for obtaining poly(n)-factor approximation algorithms for these problems. These are the first results for clustering problems in the k -machine model. We assume that the metric provided as input for these clustering problems in only implicitly provided, as an edge-weighted graph and in a nutshell, our main technical contribution is to show that constant-factor approximation algorithms for all three clustering problems can be obtained by learning only a small portion of the input metric.