Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

By Kamal Kumar Jain, Mohammad Mahdian, Evangelos K. Markakis, Amin Saberi, Vijay V. Vazirani. JACM, 2002

509 citations recorded by the source corpus.

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n3), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

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

View Paper: https://www.semanticscholar.org/paper/c0e91c479105204f64fd90619ce37bcc927f4471

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

Local search heuristic for k-median and facility location problems (2001, methodology): “Jain et al. [ 10 ] used the method of dual fitting and factor revealing LP to design two greedy algorithms for the UFL problem with approximation guarantees of 1.861, 1.61 and running times of O(m log m), O(n3), respectively, where”
AdWords and generalized on-line matching (2005, methodology): “This concept builds on the notion of a factor-revealing LP [Jain et al. 2003].”
The Design of Approximation Algorithms (2011, background): “17 is due to Jain, Mahdian, Markakis, Saberi, and Vazirani [176], following work of Guha and Khuller [146] for the hardness of the uncapacitated facility location problem.”
A 1.488 approximation algorithm for the uncapacitated facility location problem (2011, background): “After that, a large number of constant approximation algorithms have been proposed([4], [9], [3], [7], [8], [11]).”
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs (2006, methodology): “To prove an approximation ratio of 2, we use the technique of factor-revealing linear programs [4, 6], which is a simple generalization of a method often used to provide bounds for approximation algorithms.”
Local Search Heuristics for k-Median and Facility Location Problems (2004, methodology): “Jain et al. [10] used the method of dual fitting and factor revealing LP to design two greedy algorithms for the UFL problem with approximation guarantees of 1.861, 1.61 and running times of O(m log m), O(n 3 ), respectively, where n is the number of vertices and m is the number of edges in the unde”
Secretaries with Advice (2020, methodology): “They were introduced in the context of designing approximation algorithms for the facility location problem, in conjunction with the dual fitting technique [20].”
The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2006, background): “There are also various constant-factor approximation algorithms for the related k-median problem [26, 7, 6, 25, 37], which also yield approximation algorithms for k-means, and have running time polynomial in n, k and the dimension; recently Kanungo et al.”
Online Matching and Ad Allocation (2013, methodology): “Minimizing the objective function ∑ txt over this polytope, we get a lower bound on the performance of the algorithm on the worst possible input for the algorithm; this technique is known as a Factor-Revealing LP technique (introduced in [52, 57, 75]): ALG = ∑ txt ≥ ( 1 − (1)e ) n.”
Secretary Problems via Linear Programming (2010, methodology): “Our linear programming technique is similar to the technique of factor revealing linear programs that have been used successfully in many different settings [7, 12, 14, 19].”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, background): “Now we will construct a nonlinear program which bounds the ratio between the total connection cost and the cost of the bi-point solution.”
Bird Species Categorization Using Pose Normalized Deep Convolutional Nets (2014, background): “A nice property of facility location problems is that, unlike some clustering algorithms like k-means, a fast greedy algorithm [25] has good approximation guarantees (1.”