An Improved Local Search Algorithm for k-Median
An Improved Local Search Algorithm for k-Median
复制标题
一种改进的k-中值局部搜索算法
DOI：
10.1137/1.9781611977073.65
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Saulpic, David
中科院分区：
文献类型：
--
作者：
Cohen-Addad, Vincent;Gupta, Anupam;Hu, Lunjia;Oh, Hoon;Saulpic, David
提出了一种新的局部搜索算法来解决中位数聚类问题。我们证明了该算法的局部最优给出了(2.836 +)-近似；我们的结果改进了Arya等人[AGK+01]的(3 +)-近似局部搜索算法。此外，对自然扩展的计算机辅助分析表明，这种方法可能比最著名的近似保证方法有改进。我们算法中的新成分是基于每个客户最近和次近设施的潜在函数的使用。具体来说，潜力是所有客户的总和，客户到最近设施的距离加上（一个小常数乘以）到第二最近设施的截短距离。只有当后者可以通过交换一定数量的设施来获得，并且潜力小于前者时，我们才会从一个解决方案转移到另一个解决方案。这种改进的潜力使我们能够避免Arya等人给出的仅基于解决方案成本的局部搜索算法的糟糕局部最优。
We present a new local-search algorithm for thek-median clustering problem. We show that local optima for this algorithm give a (2.836 +∊)-approximation; our result improves upon the (3 +∊)-approximate local-search algorithm of Arya et al. [AGK+01]. Moreover, a computer-aided analysis of a natural extension suggests that this approach may lead to an improvement over the best-known approximation guarantee for the problem.The new ingredient in our algorithm is the use of a potential function based on both the closest and second-closest facilities to each client. Specifically, the potential is the sum over all clients, of the distance of the client to its closest facility, plus (a small constant times) the truncated distance to its second-closest facility. We move from one solution to another only if the latter can be obtained by swapping a constant number of facilities, and has a smaller potential than the former. This refined potential allows us to avoid the bad local optima given by Arya et al. for the local-search algorithm based only on the cost of the solution.