Local search heuristic for k-median and facility location problems

By Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit. Symposium on the Theory of Computing, 2001

391 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/124aade893a5f4a246f1587a54db37cc3f2b1aaa

How researchers see this paper

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

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

In Organizational Behavior and Human Resource Management

Citations in the corpus

Better streaming algorithms for clustering problems (2003, neutral): “Recent research has led to the development of very good approximation algorithms for this problem [4, 9, 23, 8, 5 ]. Another classical clustering objective is k–Center, where the goal is to find k centers that minimize the maximum distance of a point to its closest center.”
A local search approximation algorithm for k-means clustering (2002, background): “[5].”
On coresets for k-means and k-median clustering (2004, background): “[7], to C0 and S, where the set of candidate points is S.”
Online facility location (2001, methodology): “Similar local search techniques were extended to a number of related problems by Chudak and Williamson [6], by Arya, Garg, Khandekar, Pandit, Meyerson, and Munagala [1] and by Pál, Tardos, and Wexler [12].”
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002, methodology): “The k-median problem is studied extensively [Arya et al. 2001; Charikar and Guha 1999; Charikar et al. 1999; Jain and Vazirani 1999] and the best known approximation algorithm for this problem, due to Arya et al. [2001], achieves a factor of 3+ 2.”
Clustering Data Streams: Theory and Practice (2003, neutral): “…abundant literature on these, books [45], [62], [55], provable algorithms [41], [49], [54], [53], [71], [31], [16], [15], [6], [52], [47], [14], [59], [7], [46], the running time of provable clustering heuristics [21], [10], [42], [34], [73], [60], and special metric spaces [6], [52], [43], [68].”
A constant-factor approximation algorithm for the k-median problem (extended abstract) (1999, background): “Most recently, Arya, Garg, Khandekar, Meyerson, Munagala, and Pandit [2] showed that the natural local search heuristic that interchanges p locations as centers/non-centers is guaranteed to find a solution that is within a factor of 3 + (2/p), for any positive integer p.”
A new greedy approach for facility location problems (2002, methodology): “The k-median problem is studied extensively [2, 4, 5, 18] and the best known approximation algorithm for this problem, due to Arya et al.”
Maintaining variance and k-medians over data stream windows (2003, background): “There is a large body of previous work on k–median clustering [1, 5, 15, 16, 17, 18, 19].”