Local Search Heuristics for k-Median and Facility Location Problems

By Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit. 2004

698 citations recorded by the source corpus.

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

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

Proportionally Fair Clustering (2019, methodology): “sic context for clustering work (Gonzalez, 1985; Shmoys et al., 1997; Charikar et al., 2002; Arya et al., 2004), and is perhaps best known as the setting for the celebrated k-means heuristic (independently discovered many times, see (Jain, 2010) for a brief history).”
Differentially private combinatorial optimization (2009, background): “[1]) For any set F ⊆ V with |F | = k, there exists a set of k swaps (x1, y1), .”
Fair Clustering Through Fairlets (2018, methodology): “To solve the k -median problem we use the single swap algo-rithm due to Arya et al. (2004), which also gets a 5-approximation in the worst case, but performs much better in practice (Kanungo et al. , 2002).”
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].”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, background): “, by the local swap (Kanungo et al., 2002; Arya et al., 2004), careful seeding (Arthur & Vassilvitskii, 2007), or enumeration via sample-based loss estimator (Kumar et al.”
A local search approximation algorithm for k-means clustering (2002, background): “[4], but using our different notion of capturing.”
The Design of Approximation Algorithms (2011, background): “Arya, Garg, Khandekar, Meyerson, Munagala, and Pandit [24] first proved a performance guarantee of 5 for a local search algorithm for the k-median problem.”
Fair Algorithms for Clustering (2019, background): “The case of p = { 1 , 2 , ∞} has been extensively studied in the literature [6,9,11,16,17,25,27,29,35].”
The controller placement problem (2012, background): “…propagation latency for a placement of controllers S is: Lavg(S ) = 1 n v∈V min (s∈S ) d(v, s) (1) In the corresponding optimization problem, minimum kmedian [6], the goal is to find the placement S from the set of all possible controller placements S, such that |S | = k and Lavg(S ) is minimum.”
Better streaming algorithms for clustering problems (2003, neutral): “Copyright 2003 ACM 1-58113-674-9/03/0006 ...$5.00. particular, the streaming model has received a lot of attention [3, 27, 18, 13, 22, 16, 15, 14, 1].”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, methodology): “Following this, a local search–based (3 + )-approximation algorithm was developed by Arya et al. [2004]. Recently, Li and Svensson’s breakthrough work gave a (1 + √3 + )-approximation algorithm for k-median [Li and Svensson 2013]. To accomplish this, they defined an α-pseudo-approximation algorithm ”
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.”
An Algorithm for Online K-Means Clustering (2014, background): “It gives a constant approximation ratio and is based on local search ideas popular in the related area of design and analysis of algorithms for facility location problems, e.g., [6].”