Back to Search
Start Over
Approximation algorithms for clustering with dynamic points.
- Source :
-
Journal of Computer & System Sciences . Dec2022, Vol. 130, p43-70. 28p. - Publication Year :
- 2022
-
Abstract
- We study two generalizations of classic clustering problems called dynamic ordered k-median and dynamic k-supplier , where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k -median under mild assumptions on the input. We give a 3-approximation for dynamic k -supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 130
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 158609310
- Full Text :
- https://doi.org/10.1016/j.jcss.2022.07.001