Algorithms for facility location problems with outliers

By Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan. ACM-SIAM Symposium on Discrete Algorithms, 2001

464 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/0b490334ae4d06330bcfecbf7184b7c458a1f6e9

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

k-means-: A Unified Approach to Clustering and Outlier Detection (2013, unknown): “Section 6 is a short conclusion.”
Local Search Methods for k-Means with Outliers (2017, unknown): “Using empirical evaluation on both synthetic and large-scale real-world data, we demonstrate that the algorithm dominates recently proposed heuristic approaches for the problem.”
On the cost of essentially fair clusterings (2018, background): “The wide applicability of k -center has given rise to numerous variants that strive to incorporate useful con-19 straints into the solution, such as capacity constraints [10, 15, 24], lower bounds on the size of each cluster [3, 6] or allowing for outliers [12, 16].”
Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation (2001, background): “VAZIRANI, V. V. 1995.”
A Unified Approach to Approximating Partial Covering Problems (2006, background): “Therefore, it cannot be directly applied to partial covering problems with a compact implicit representation of exponentially many sets, such as facility location with outliers [7], k-MST [17], k-Steiner forest [22], etc.”
A unified framework for approximating and clustering data (2011, methodology): “Bicriteria approximation was also used as a starting point for computing clustering in the setting of outliers and penalties; see [7, 11].”
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002, methodology): “Their algorithm was adapted for solving several related problems such as the faulttolerant and outlier versions, and the k-median problem [Jain and Vazirani 1999, 2000; Charikar et al. 2001].”
Communication-Optimal Distributed Clustering (2016, background): “In the alternative blackboard model, the coordinator is simply a blackboard where these s sites P 1 , . . . , P s can share information; in other words, if one site sends a message to the coordinator/blackboard then all the other s − 1 sites can see this information without further communication.”