TY - GEN

T1 - An Improved Local Search Algorithm for k-Median

AU - Cohen-Addad, Vincent

AU - Gupta, Anupam

AU - Oh, Lunjia Hu Hoon

AU - Saulpic, David

N1 - Publisher Copyright:
Copyright © 2022 by SIAM Unauthorized reproduction of this article is prohibited.

PY - 2022

Y1 - 2022

N2 - We present a new local-search algorithm for the k-median clustering problem. We show that local optima for this algorithm give a (2.836 + ϵ)-approximation; our result improves upon the (3 + ϵ)-approximate localsearch 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.

AB - We present a new local-search algorithm for the k-median clustering problem. We show that local optima for this algorithm give a (2.836 + ϵ)-approximation; our result improves upon the (3 + ϵ)-approximate localsearch 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.

UR - http://www.scopus.com/inward/record.url?scp=85128213546&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85128213546&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85128213546

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1556

EP - 1612

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -