Dynamic Clustering to Minimize the Sum of Radii
- PDF / 2,081,377 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 133 Views
Dynamic Clustering to Minimize the Sum of Radii Monika Henzinger1 · Dariusz Leniowski1 · Claire Mathieu2 Received: 11 October 2018 / Accepted: 29 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem. Keywords Dynamic algorithm · Clustering in metric space · Approximation · Doubling dimension
1 Introduction The main goal of clustering is to partition a set of objects into homogeneous and well separated subsets (clusters). Clustering techniques have long been used in a wide variety of application areas, see for example the excellent surveys [24, 29]. There are several ways to model clustering. Among them, the problem of sumof-radii (or sum-of-diameter) clustering has been extensively studied: the clients are located in a metric space and one must open facilities to minimize facility opening cost (or keep the number of open facilities limited to at most k) plus the sum of the cluster radii (or, in other applications, cluster diameters). To give a concrete example, imagine a telecommunications agency setting up mobile towers that provide * Monika Henzinger [email protected] Dariusz Leniowski [email protected] Claire Mathieu [email protected] 1
Faculty of Computer Science, University of Vienna, Vienna, Austria
2
IRIF, CNRS, Université de Paris, Paris, France
13
Vol.:(0123456789)
Algorithmica
wireless access to selected clients, incurring costs for setting up towers as well as for configuring a tower to serve the customers lying within a certain distance, where that latter contribution to the cost increases with the maximum distance served by the tower. Assume the number of facilities is limited to k. For sum-of-diameter clustering, Doddi et al. [17] prove hardness of approximation to within better than a factor of 2. More recently, NP-hardness was proved for the sum-of-radii problem even for shortest path metrics on weighted planar graphs [28], or, in the case of sum-of-diameters, even for metrics of constant doubling dimension [19]. Turning to approximation algorithms, Charikar and Panigraphy [15] design and analyze an O(1) approximation algorithm for sum-of-radii and for sum-of-diameter clustering with k clusters. They start from a linear-programming relaxation, use a primal–dual type approach and, along the way, design a bicriteria algorithm. They also design an incremental alg
Data Loading...
