论文标题
用动态点聚类的近似算法
Approximation Algorithms for Clustering with Dynamic Points
论文作者
论文摘要
我们研究了经典聚类问题的两个概括，称为动态订购$ k $ -Median和Dynamic $ k $ -supplier，需要聚类随着时间的推移而发展，我们可以在连续时间步长之间移动群集中心。在这些动态的聚类问题中，总体目标是最大程度地减少点的某些服务成本和中心运动成本的组合，或者将一个受试者最小化，而对另一个主题的某些限制。在输入中的轻度假设下，我们获得了动态有序$ k $米德的恒定因素近似算法。我们为动态$ k $ supplier提供了3个Approximation，以及其异常版本的多标准近似值，当时间步长的数量为两个时，可以丢弃某些点。我们通过几乎匹配的硬度结果来补充算法。
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.
