تقرير
$k$-Center Clustering in Distributed Models
| العنوان: | $k$-Center Clustering in Distributed Models |
|---|---|
| المؤلفون: | Biabani, Leyla, Paz, Ami |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms |
| الوصف: | The $k$-center problem is a central optimization problem with numerous applications for machine learning, data mining, and communication networks. Despite extensive study in various scenarios, it surprisingly has not been thoroughly explored in the traditional distributed setting, where the communication graph of a network also defines the distance metric. We initiate the study of the $k$-center problem in a setting where the underlying metric is the graph's shortest path metric in three canonical distributed settings: the LOCAL, CONGEST, and CLIQUE models. Our results encompass constant-factor approximation algorithms and lower bounds in these models, as well as hardness results for the bi-criteria approximation setting. Comment: Presented in SIROCCO'24 conference |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2407.18031 |
| رقم الأكسشن: | edsarx.2407.18031 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |