ICML 2024 | 设施选址问题在高维欧氏空间的动态算法
关键词：动态算法，高维欧氏空间，设施选址
导 读
本文是 ICML 2024 入选论文 DynamicFacility Location in High Dimensional Euclidean Spaces 的解读。该论文作者遵循姓氏排名，由华威大学 Sayan Bhattacharya 教授、维也纳大学 Gramoz Goranci 教授、北京大学助理教授姜少峰、北京大学图灵班本科生钱易以及北京大学计算机学院博士生张宇博合作完成。
本工作提出了动态 Near Neighbor Indicator 这一数据结构，并基于其设计了首个设施选址问题在高维欧氏空间中的亚线性动态算法。
01
引 言
设施选址问题是计算机科学和运筹学等领域的经典优化问题，并且由于与 -median 等基于中心的聚类的密切联系，在聚类算法研究中也成为了重要的基本问题。
对于给定度量空间中的设施选址问题，对于一个点集 ，我们需要选出一个设施集合 ，对于 中的每个点以 的代价开设一个设施。我们的目标是最小化设施开设代价与连接代价（ 中的每个点到距离其最近的设施的欧式距离之和），即最小化： 其中 表示在给定度量空间中， 到 中的最近点的距离。
在本文中，我们研究了在高维欧式空间中设施选址问题的动态算法，即我们会在点集 中进行多次插入或者删除点的操作，在动态操作下，我们需要显式维护设施集合 与所需代价。
02
结 果
本工作给出了第一个对高维空间适用的、 -近似的、达到常数稳定性的、更新时间是亚线性于 的动态算法。论文的结果可以更一般地适用于一切具有高效最近邻查询数据结构的空间。其中，对于动态算法来说，我们使用设施集合 的变化量来衡量稳定性。
具体来说，在高维欧式空间中，对于任何 ，我们的算法可以以 的近似比， 的均摊时间插入或者删除一个点，并且具有 的均摊稳定性。
在一般的度量空间中，插入或者删除一个点具有线性时间的下界，但是如果存在动态近似最近邻 oracle，我们也可能可以给出更新时间为亚线性的算法。
03
算法技术
在本文中，我们将先介绍一个快速的静态算法，再讲解如何将静态算法动态化。
静态算法
本静态算法基于 Mettu-Plaxton [4] 算法来计算估值。在 Mettu-Plaxton 算法中，对于每个输入中的点 ，我们需要计算得出一个值 ，所有的 之和即为最优解的 近似，并且 有助于构建设施集合。
对于 的计算，我们有较为方便的 近似算法。不妨假设开设设施的代价 ，此时我们只我们需要找到一个 ，使得 （其中 ），并将 作为 的近似值。使用本方法，找到一个为整数的 即可达到 近似。
在高维欧式空间中，我们具有动态近似最近邻工具 [3]。基于最近邻 oracle，我们可以加速 值的计算。通过以 的概率保留 中的每个点，并借助最近邻查询算法，判断保留下来的点邻域中是否存在其它点，进行 次采样，每个点会高概率被采样 次，因此我们可以较为准确地评估距离 不超过 的点个数，进而可以快速计算 的近似值 。通过该手段，我们可以得到一个 时间的用于计算 近似最小代价的静态算法。
对于设施集合，我们基于 [2] 中提出的算法来求解。
对于该算法，我们可以对每个点 找一个整数 ，使得 ，令 。如果我们用此方法得出的 替代 ，我们依然可以得到良好的近似解。此时，我们可以证明，若 ，那么此时满足 且 的 个数高概率是 级别的，因此我们可以对 中的点以 的概率进行子采样，加入 中的点，通过判断一个点周围是否存在近邻，来找出所有符合 (S1) 条件的 。
因此，通过借助最近邻 oracle，我们可以得到一个 时间的用于求解 近似最小代价与开设设施集合的静态算法。
动态算法
对于一般的动态最近邻 oracle，对于 ，我们可以维护一个点集 ，支持插入或者删除点， 以及询问一个点的最近点距离它是否 。
本文中，我们提出了一种新的数据结构：Near Neighbor Indicator。它相较于一般的最近邻 oracle，它能够在每次插入或者删除点后，它会对每一个点 显示维护 表示其最近点距离它是否 ，也即会报告发生变化的 ，根据本论文提出的方法，我们可以只进行均摊 次动态最近邻查询即可，并且 发生变化的次数也为均摊 。
根据论文中所提出的 Near Neighbor Indicator，我们只需将静态算法中所使用的动态最近邻 oracle 替换为 Near Neighbor Indicator，即可自然的得到完全动态算法，并且依然具有良好的近似比与时间复杂度。
Near Neighbor Indicator
Near Neighbor Indicator 是本工作的重要贡献之一，如上文所说，对于一个固定的参数 ，我们维护了一个点集 ，会对每一个点 显示维护 表示其最近点距离它是否 。
对于一系列的插入删除操作，我们维护了当前点集 的一个划分： ，它们两两不交且并为全集。其中 为 remote 点集， 为 cluster 集， 为 alive 点集。其中 中的点不存在距离 的近邻。 则进一步被划分为若干个 cluster，每个 cluster 中的点互相距离都十分接近。对于每个 中的点，它都对应一个距离 的 中的点，且每个 中的点最多对应一个 类点。
下图为一种合法情况，其具有两个簇： ，其中 与 对应， 与 对应。
假设我们需要插入点 ，如果 存在来自 中的近邻，则我们可以以 与其在 中的近邻新建一个簇的方式来维护我们的数据结构。
如果其存在来自 中的近邻 ，只需将 与 单独新建为一个簇即可。
如果其存在来自 中的近邻 ，若 仍未对应 类点，则将 与 对应，否则将 与 在 中的对应点新建为一个簇即可。
如果其与没有来自 中的近邻，直接将其设置为 类点即可。
如果我们需要删除点 ，如果 ，我们直接删除即可，如果其来自 ，且簇大小为 ，则簇中另外一个点可能会受到影响，我们只需重新插入即可修正。
综上所述，我们仅仅需要维护 上的动态最近邻 oracle，通过势能分析，我们可以得到我们的均摊询问次数与其他部分时间复杂均为 ，并且我们只需根据点是否来自点集 即可得知其是否存在近邻，这是容易显示维护的。
稳定性
根据 [1] 中提出的定理：如果存在 近似，在 的均摊时间更新的动态设施选址算法，那么就存在一个 近似， 均摊更新时间的，具有 稳定性的设施选址算法。因此，我们论文中的算法可以直接得出对应的具有 稳定性的设施选址算法。
04
实验结果
我们将我们的算法与 Mettu-Plaxton 算法 [4]（在每次插入与删除后重新运行）进行了对比，在四组不同的数据集上，我们采用滑动窗口的方式进行插入与删除，测试结果如下：
由测试结果我们可以得知，我们的算法在维护的解的代价方面，略差于 MP 算法，但相差无几，并且我们算法在测试集上表现出了良好的稳定性。除此之外，我们的算法在运行效率上也比 MP 算法快了约两个数量级。
05
总 结
在这项研究中，我们提出了 Near Neighbor Indicator Structure，并凭借其设计了首个设施选址问题在高维欧氏空间的亚线性动态算法，在若干数据集的测试之下，我们的算法也表现出了优异的效果，在效率上有极大的提升。除此之外，我们提出的 Near Neighbor Indicator Structure 为相关高维动态算法提供了新的思路，也提供了新的工具与手段。
参考文献
[1] Cohen-Addad, V., Hjuler, N., Parotsidis, N., Saulpic, D., and Schwiegelshohn, C. Fully dynamic consistent facility location. In NeurIPS 2019.
[2] Czumaj, A., Gao, G., Jiang, S. H., Krauthgamer, R., and Vesely, P. Fully scalable MPC algorithms for clustering in high dimension. In ICALP 2024.
[3] Har-Peled, S., Indyk, P., and Motwani, R. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput., 8(1):321–350, 2012.
[4] Mettu, R. R. and Plaxton, C. G. The online median problem. In 41st Annual Symposium on Foundations of Computer Science, In FOCS 2000.
图文 | 钱易
北京大学姜少峰课题组
姜少峰课题组近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。