An Improved Local Search Algorithm for k-Median

Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu Hoon Oh, David Saulpic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages1556-1612
Number of pages57
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'An Improved Local Search Algorithm for k-Median'. Together they form a unique fingerprint.

Cite this