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

2001/03/01 by Kamal Jain, Vijay V. Vazirani · 35 citations
Business, Management and Accounting · Computer Science · Engineering · #Facility Location and Emergency Management #Complexity and Algorithms in Graphs #Vehicle Routing Optimization Methods

paper · doi:10.1145/375827.375845

Abstract

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k -median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m ) and O(m log m(L + log ( n ))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.

Cited by

• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework
• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
• Local Search Heuristics for k-Median and Facility Location Problems
• Incremental Clustering and Dynamic Information Retrieval
• Uniform Capacitated Facility Location Problems with Penalties/Outliers
• FPT Approximation Schemes for Maximizing Submodular Functions
• Clustering with Label Consistency
• A Broader View on Clustering under Cluster-Aware Norm Objectives
• On Tight FPT Time Approximation Algorithms for k-Clustering Problems
• Approximating k-Forest with Resource Augmentation: A Primal-Dual\n Approach
• Facility Location for Congesting Commuters and Generalizing the Cost-Distance Problem
• Coresets for Clustering in Excluded-minor Graphs and Beyond
• A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
• Differentially Private Wasserstein Barycenters
• k-means++: few more steps yield constant approximation
• Clustering in Varying Metrics
• Euclidean Prize-collecting Steiner Forest
• Differentially Private Clustering: Tight Approximation Ratios
• A Systematic Approach to Bound Factor-Revealing LPs and its Application\n to the Metric and Squared Metric Facility Location Problems
• Consistent k-Median: Simpler, Better and Robust
• Online Learning of Facility Locations
• New Results on the Fault-Tolerant Facility Placement Problem
• We Are Impatient: Algorithms for Geographically Distributed Load\n Balancing with (Almost) Arbitrary Load Functions
• On the Factor Revealing LP Approach for Facility Location with Penalties
• Approximation Algorithms for Socially Fair Clustering
• Centrality of Trees for Capacitated k-Center
• A Polynomial-Time Approximation Scheme for Facility Location on Planar\n Graphs
• Capacitated Center Problems with Two-Sided Bounds and Outliers
• Polynomial Time Algorithm for 2-Stable Clustering Instances
• Prize-collecting Network Design on Planar Graphs
• On Distributed Algorithms for Cost-Efficient Data Center Placement in Cloud Computing
• Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques
• Scalable distributed service migration via Complex Networks Analysis
• Generalized Load Balancing and Clustering Problems with Norm Minimization

Related

• Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
• Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP
• A (2+ε)-Approximation Algorithm for Metric k-Median
• A Distributed Approximation Algorithm for the Metric Uncapacitated Facility Location Problem in the Congest Model
• Facility Location on High-dimensional Euclidean Spaces