A constant-factor approximation algorithm for the k-median problem (extended abstract)

By Moses Charikar, Sudipto Guha, É. Tardos, David B. Shmoys. 1999

How researchers see this paper

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

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).”
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.”
Local Search Heuristics for k-Median and Facility Location Problems (2004, methodology): “A different approach to facility location was employed by Shmoys, Tardos, and Aardal [20] and Charikar et al. [5].”
Clustering Large Graphs via the Singular Value Decomposition (2004, methodology): “For the k-median problem, good approximation algorithms have been hard to come by; most notably ( Charikar et al., 2002 ) gave a constant factor approximation algorithm based on a rounding procedure for a natural linear programming relaxation.”
Edge server placement in mobile edge computing (2019, background): “The challenge associated with such placements are determining 1) the locations in which edge servers should be placed, and 2) which base stations should be assigned to which edge servers, which we show to be an NP-hard problem.”
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation (2001, unknown): “8 [Charikar et al. 1999].”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “The idea of robustifying the Lloyd’s algorithm is not new (e.g. see[10, 11] and the references therein) and several robust Lloyd algorithms are empirically well studied.”
On coresets for k-means and k-median clustering (2004, background): “[12] proposed the first constant factor approximation to the problem for an arbitrary metric space using a natural linear programming relaxation of the problem followed by rounding the fractional solution.”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, background): “rk. Finally, we consider the problem of Clustering multi-dimensional data. This problem has received much attention in the traditional computational settings (polynomial-time approximation algorithms [22, 14, 6, 29, 15, 17]. More to the point here, it is an important problem for many modern large da”
Online facility location (2001, background): “Facility location has been the subject of a great deal of previous work [13, 3, 2, 8, 7, 4, 5] in an offline setting, where all the demand points are known ahead of time.”