Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

By Kamal Kumar Jain, Vijay V. Vazirani. JACM, 2001

873 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Industrial and Manufacturing Engineering, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/1add794ba468395711fa3e1c5899e7675ba27783

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 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 and Vazirani [ 11 ] obtained a 4 approximation algorithm for ∞-CFL when the capacities were nonuniform by solving a related UFL problem using their primal-dual algorithm.”
A discriminative framework for clustering via similarity functions (2008, methodology): “In the Algorithms literature, clustering is typically stud ie by posing some objective function, such as k-median, min-sum or k-means, and then developing algorithms for approximately o ptimizing this objective given a data set represented as a wei ghted graph [12, 24, 22].”
The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2006, background): “There are also various constantfactor approximation algorithms for the related k-median problem [26, 7, 6, 25, 37], which also yield approximation algorithms fork-means, and have running time polynomial in n, k and the dimension; recently Kanungo et al.”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, methodology): “Then, Jain and Vazirani [20] applied Lagrangian Relaxation to remove the hard constraint of opening at most k facilities, effectively reducing the problem to an easier version known as the Uncapacitated Facility Location (UFL) problem.”
Local Search Heuristics for k-Median and Facility Location Problems (2004, methodology): “Jain and Vazirani [11] obtained a 4 approximation algorithm for ∞-CFL when the capacities were nonuniform by solving a related UFL problem using their primal-dual algorithm.”
A Unified Approach to Approximating Partial Covering Problems (2006, methodology): “To simplify the presentation, it is convenient to state our approach in terms of the Lagrangian relaxation technique, which was first utilized in the context of approximation algorithms by Jain and Vazirani [25].”
The Design of Approximation Algorithms (2011, background): “8 is from Jain and Vazirani [177]; Exercise 7.”
Correlation Clustering (2002, methodology): “The analysis is fairly standard (much like the generic transformation of Kearns (1998) in the machine learning context, and even closer to the analysis of Condon and Karp for graph partitioning (Condon & Karp, 1999)).”
A combinatorial, primal-dual approach to semidefinite programs (2007, background): “Some canonical examples are network design problems [3] (or see the survey [14]) and O(1)-approximation for k-median (LP-based algorithm in [11]; faster primal-dual algorithm in [18]).”