Primal-dual approximation algorithms for metric facility location and k-median problems

By Kamal Kumar Jain, Vijay V. Vazirani. 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): “Interestingly, the ostensibly similar primal-dual approach of [24] does not appear amenable to the added constraint of proportionality (in particular, the reduction to facility location from [24] is no longer straightforward).”
Influence sets based on reverse nearest neighbor queries (2000, methodology): “Better approximations exist, but they are based on Linear Programming [10].”
Clustering Large Graphs via the Singular Value Decomposition (2004, methodology): “The constant has been improved in Jain and Vazirani (1999) and further in Charikar and Guha (1999) using the primal-dual method.”
Local search heuristic for k-median and facility location problems (2001, methodology): “JainandVazirani[6]obtaineda4approximationalgorithmforo-CFLwhentheapaitieswere non-uniformbysolvingarelatedUFLproblemusing theirprimal-dualalgorithm.”
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.”
Provisioning a virtual private network: a network design problem for multicommodity flow (2001, result): “We also note that our facility location problem, while new, is related to previous work on the classical facility location problem [21, 14 , 5] and its variants like multi-level and load-balanced facility location [1, 12].”
Achieving anonymity via clustering (2006, background): “The above formulation is similar to the primal-dual formulation of facility location [9].”
On coresets for k-means and k-median clustering (2004, background): “It was observed that if the constraint of having exactly k-medians is relaxed, the problem becomes considerably easier [11, 24].”
Analysis of a local search heuristic for facility location problems (2000, methodology): “Recent work also includes fast (6; 1)-and 3-approximation algorithms for UKM and UFL, respectively, that Jain and Vazirani 14] have obtained using an elegant primal-dual approach.”
Algorithms for facility location problems with outliers (2001, background): “As in the proof of Jain and Vazirani, we charge the facility cost F and connection cost C to the dual variables oq as follows.”
A constant-factor approximation algorithm for the k-median problem (extended abstract) (1999, methodology): “Jain & Vazirani [20] give an extremely elegant primal-dual 3-approximation algorithm for the uncapacitated facility location problem, and show how to use that procedure to obtain a 6-approximation algorithm for the k-median problem.”
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002, methodology): “The primal-dual algorithm of Jain and Vazirani [22] is versatile in that it can be used to obtain algorithms for many variants of the facility location problem, such as k-median [22], a common generalization of k-median and facility location [22], capacitated facility location with soft capacities [”
On the placement of Web server replicas (2001, background): “median problem. Jain & Vazirani [ 15 ] and Charikar and Guha [6] subsequently improved this initial result, giving 6- and 4approximation algorithms, respectively.”
Clustering Data Streams: Theory and Practice (2003, methodology): “Use the primal dual algorithm [47] to cluster the final O (cid:133) M (cid:134) medians to k medians.”
A new greedy approach for facility location problems (2002, methodology): “Jain and Vazirani [18] show that their facility location algorithm gives rise to a 4-approximation algorithm for the metric capacitated facility location problem with soft capacities.”
Correlation clustering in general weighted graphs (2006, background): “(k-clustering) [11], minimizing the average distance between pairs of clustered points (k-clustering sum) [24], minimizing the maximum distance to a “centroid object’’ chosen for each cluster (k-center) [11], minimizing the average distance to such a centroid object (k-median) [13], minimizing the a”
Clustering data streams (2000, methodology): “In the recent past, several approximation algorithms have been proposed for the k{Median problem [3, 10, 2].”