We study the $k$-center problem in a kinetic setting: given a set of continuously moving points $P$ in the plane, determine a set of $k$ (moving) disks that cover $P$ at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model allows positive results only for $k<3$. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of $k$-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution -- the topological stability ratio -- considering various metrics and various optimization criteria. For $k = 2$ we provide tight bounds, and for small $k > 2$ we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant $k$.
翻译:在动能环境中,我们研究美元中心问题:鉴于飞机上一组不断移动的点数(P美元),我们确定一套每步每步都覆盖美元(P美元)的美元(移动)磁盘(移动)盘数,这样磁盘在任何时刻都尽可能小。尽管时间的最佳解决办法可能出现不连续的变化,但许多实际应用都需要稳定的解决办法:磁盘必须随时间平稳移动。关于这一问题的现有结果要求磁盘以约束速度移动,但这种模式只允许美元(P美元)取得积极结果。因此,结果有限,很少提供理论见解。相反,我们研究美元中间点的表面稳定性。最近引入了地形稳定性,只需要不断改变的解决办法,但可能任意地如此快。我们证明最佳但不稳定的解决方案的辐射与表面稳定解决方案的辐射之间的比率上下限是:表面稳定比率 -- -- 表面稳定比率 -- -- 考虑各种计量和各种优化标准。对于美元来说,结果是有限的。对于美元=2美元,我们提供了紧凑的固定比率,最后,我们提供了一个固定的顶端值为2美元。