Deng, Shichuan ;
Li, Jian ;
Rabani, Yuval
Approximation Algorithms for Clustering with Dynamic Points
Abstract
In many classic clustering problems, we seek to sketch a massive data set of n points (a.k.a clients) in a metric space, by segmenting them into k categories or clusters, each cluster represented concisely by a single point in the metric space (a.k.a. the cluster’s center or its facility). The goal is to find such a sketch that minimizes some objective that depends on the distances between the clients and their respective facilities (the objective is a.k.a. the service cost). Two notable examples are the kcenter/ksupplier problem where the objective is to minimize the maximum distance from any client to its facility, and the kmedian problem where the objective is to minimize the sum over all clients of the distance from the client to its facility.
In practical applications of clustering, the data set may evolve over time, reflecting an evolution of the underlying clustering model. Thus, in such applications, a good clustering must simultaneously represent the temporal data set well, but also not change too drastically between time steps. In this paper, we initiate the study of a dynamic version of clustering problems that aims to capture these considerations. In this version there are T time steps, and in each time step t ∈ {1,2,… ,T}, the set of clients needed to be clustered may change, and we can move the k facilities between time steps. The general goal is to minimize certain combinations of the service cost and the facility movement cost, or minimize one subject to some constraints on the other. More specifically, we study two concrete problems in this framework: the Dynamic Ordered kMedian and the Dynamic kSupplier problem. Our technical contributions are as follows:
 We consider the Dynamic Ordered kMedian problem, where the objective is to minimize the weighted sum of ordered distances over all time steps, plus the total cost of moving the facilities between time steps. We present one constantfactor approximation algorithm for T = 2 and another approximation algorithm for fixed T ≥ 3.
 We consider the Dynamic kSupplier problem, where the objective is to minimize the maximum distance from any client to its facility, subject to the constraint that between time steps the maximum distance moved by any facility is no more than a given threshold. When the number of time steps T is 2, we present a simple constant factor approximation algorithm and a bicriteria constant factor approximation algorithm for the outlier version, where some of the clients can be discarded. We also show that it is NPhard to approximate the problem with any factor for T ≥ 3.
BibTeX  Entry
@InProceedings{deng_et_al:LIPIcs:2020:12903,
author = {Shichuan Deng and Jian Li and Yuval Rabani},
title = {{Approximation Algorithms for Clustering with Dynamic Points}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {37:137:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12903},
URN = {urn:nbn:de:0030drops129037},
doi = {10.4230/LIPIcs.ESA.2020.37},
annote = {Keywords: clustering, dynamic points, multiobjective optimization}
}
26.08.2020
Keywords: 

clustering, dynamic points, multiobjective optimization 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 