Analysis of a local search heuristic for facility location problems

By Madhukar R. Korupolu, C. Plaxton, Rajmohan Rajaraman. ACM-SIAM Symposium on Discrete Algorithms, 2000

503 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/42fd54bfa638fbaaad05dec85eb835ba71d46a3a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Organizational Behavior and Human Resource Management

Citations in the corpus

Communication-Optimal Distributed Clustering (2016, unknown): “In k-median and k-means we replace the objective function maxp∈P d(p, C) with∑ p∈P d(p, C) and ∑ p∈P (d(p, C)) 2 respectively.”
Local Search Heuristics for k-Median and Facility Location Problems (2004, background): “Korupolu, Plaxton, and Rajaraman [14] considered the operations of adding, deleting, and swapping a facility but could only prove a locality gap of at most 5.”
Private Model Compression via Knowledge Distillation (2018, methodology): “We use a 2-OPT greedy algorithm to solve this problem (Korupolu, Plaxton, and Rajaraman 1998).”
A local search approximation algorithm for k-means clustering (2002, background): “Such simple heuristics exist for the facility location and the metric k-median problems [4, 8, 26].”
A 1.488 approximation algorithm for the uncapacitated facility location problem (2011, background): “After that, a large number of constant approximation algorithms have been proposed([4], [9], [3], [7], [8], [11]).”
Local search heuristic for k-median and facility location problems (2001, methodology): “[8] considered the operations of adding, deleting and swapping a facility but could only prove a locality gap of 5.”
Algorithms for facility location problems with outliers (2001, background): “All of these optimization problems are NPhard, and polynomial time approximation algorithms have been studied (see [17, 4, 5, 6, 31, 19, 13, 15, 21, 23]).”
Online facility location (2001, methodology): “Such techniques were first analyzed by Korupolu, Plaxton, and Rajaraman [9, 10] and the analysis was later improved by Charikar and Guha [2] to give a 1+ p 2+ approximation in O(n(2)( 1 +logn)) time.”
Influence sets based on reverse nearest neighbor queries (2000, methodology): “The method of choice in practice for this problem is the greedy method { it is simple, and is a provably small approximation [14].”
Privacy preserving clustering with constraints (2018, methodology): “Signiﬁcant techniques developed during the cause of many decades are LP rounding techniques [10, 33], greedy and primal dual methods [25, 26], local search algorithms [5, 29], and, more recently, the use of pseudo-approximation [32].”
A new greedy approach for facility location problems (2002, background): “In the last decade this problem was studied extensively from the perspective of approximation algorithms [2, 4, 6, 7, 8, 13, 18, 20, 28, 30].”
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem (2003, unknown): “Further work has also been done on local search algorithms; most notably, Charikar and Guha [CG99] have given a more sophisticated neighborhood structure that is amenable to analysis to yield stronger bounds 4 F.A. CHUDAK and D.B. SHMOYS than those obtained by Korupolu, Plaxton, and Rajaraman.”
Clustering data streams (2000, methodology): “We will be interested in algorithms which use more than k medians but run in linear space [12, 2, 9].”
Primal-dual approximation algorithms for metric facility location and k-median problems (1999, methodology): “In the last few years, there has been renewed interest in tackling this problem, this time from the perspective of approximation algorithms [12, 23, 24, 27, 32].”