HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Improved Algorithms for Distributed Balanced Clustering

Abstract : We study a weighted balanced version of the k-center problem, where each center has a fixed capacity, and each element has an arbitrary demand. The objective is to assign demands of the elements to the centers, so as the total demand assigned to each center does not exceed its capacity, while the maximum distance between centers and their assigned elements is minimized. We present a deterministic O(1)-approximation algorithm for this generalized version of the k-center problem in the distributed setting, where data is partitioned among a number of machines. Our algorithm substantially improves the approximation factor of the current best randomized algorithm available for the problem. We also show that the approximation factor of our algorithm can be improved to $$5+\varepsilon $$, when the underlying metric space has a bounded doubling dimension.
Document type :
Conference papers
Complete list of metadata

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, March 10, 2021 - 4:05:08 PM
Last modification on : Wednesday, March 10, 2021 - 4:13:27 PM
Long-term archiving on: : Friday, June 11, 2021 - 7:06:27 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2023-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Kian Mirjalali, Hamid Zarrabi-Zadeh. Improved Algorithms for Distributed Balanced Clustering. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.72-84, ⟨10.1007/978-3-030-57852-7_6⟩. ⟨hal-03165380⟩



Record views