A new greedy approach for facility location problems

By Kamal Kumar Jain, Mohammad Mahdian, Amin Saberi. 2002

482 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, 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 Computational Theory and Mathematics

In Computer Networks and Communications

In Organizational Behavior and Human Resource Management

Citations in the corpus

Proportionally Fair Clustering (2019, neutral): “, 2004), primal-dual (Jain & Vazirani, 1999), and greedy dual fitting (Jain et al., 2002).”
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002, background): “(1)This paper is based on the preliminary versions [31] and [21].”
Clustering Data Streams: Theory and Practice (2003, unknown): “…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].”
Optimal Time Bounds for Approximate Clustering (2002, background): “It is wellknown that thek-median problem isNP-hard; furthermore, it is known to beNP-hard to achieve an approximation ratio better than1 + 2e [8].”
On the cost of essentially fair clusterings (2018, background): “765 -approximation [32, 11], while the best hardness result lies below two [23].”
AdWords and generalized on-line matching (2005, background): “The latter notion was implicit in [13, 4, 12] and was formalized and made explicit in [7, 6].”
A 1.488 approximation algorithm for the uncapacitated facility location problem (2011, methodology): “78)-approximation algorithm A2 proposed by Jain, Mahdian and Saberi [8], Byrka gave a 1.”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, background): “Later, Jain, Mahdian, and Saberi (JMS) improved the approximation ratio of constructing the bi-point solution to 2, resulting in a 4-approximation [19].”
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs (2006, methodology): “This technique was used in [7, 14, 15] before it was explicitly named and used in [11, 12, 16].”
Improved Approximation Algorithms for the Uncapacitated Facility Location Problem (2003, result): “Results of Jain, Mahdian, and Saberi [JMS02] and Mahdian, Markakis, Saberi, and Vazirani [MMSV01] gave a primal-dual based analysis of greedy-style algorithms.”