Local Search Heuristics for k-Median and Facility Location Problems

2004/01/01 by Vijay Arya, Naveen Garg, Rohit Khandekar +3 · 547 citations
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #1-center problem #Bounded function #Computer science #Facility Location and Emergency Management #Facility location problem #Heuristic #Heuristics #Local search (optimization) #Locality #Mathematical optimization #Mathematics #Metric (unit) #Minification #Optimization and Search Problems #Vehicle Routing Optimization Methods

paper · doi:10.1137/s0097539702416402

published in SIAM Journal on Computing 33(3), 544-562 (Society for Industrial and Applied Mathematics)

openalex publication_date 2004/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26

Abstract

We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.

Citations

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

Cited by

• Differentially Private k-Means with Constant Multiplicative Error
• Facility Location in Evolving Metrics
• A Broader View on Clustering under Cluster-Aware Norm Objectives
• K-median: exact recovery in the extended stochastic ball model
• Facility Location for Congesting Commuters and Generalizing the Cost-Distance Problem
• A PAC Approach to Application-Specific Algorithm Selection
• A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
• Fast Clustering using MapReduce
• Coresets for (k,l)-Clustering under the Fréchet Distance
• Clustering in Varying Metrics
• Fair k-Center Clustering for Data Summarization
• A lower bound for metric 1-median selection
• Differentially Private Clustering: Tight Approximation Ratios
• Probabilistic Fair Clustering
• Achieving Approximate Soft Clustering in Data Streams
• Harmonizing SAA and DRO
• Lotsize optimization leading to a p-median problem with cardinalities
• Competitively Consistent Clustering
• Content replication and placement in mobile networks
• Facility Location and k-Median with Fair Outliers
• Improved approximation for 3-dimensional matching via bounded pathwidth local search
• Centrality of Trees for Capacitated k-Center
• Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function
• A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
• MONITOROLOGY – THE ART OF OBSERVING THE WORLD
• Capacitated Center Problems with Two-Sided Bounds and Outliers
• Polynomial Time Algorithm for 2-Stable Clustering Instances
• Data Stability in Clustering: A Closer Look
• 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
• Fair Clustering with Multiple Colors
• Individual Fairness for k-Clustering
• Generalized Load Balancing and Clustering Problems with Norm Minimization
• Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problem
• Fast Noise Removal for k-Means Clustering
• A probability-based multi-path alternative fueling station location model
• Data-Driven Clustering via Parameterized Lloyd's Families
• Clustering under Perturbation Resilience
• Network Creation Games: Think Global - Act Local
• An improved approximation algorithm for k-median problem using a new factor-revealing LP
• A Unified Approach for Clustering Problems on Sliding Windows
• On Decentralized Policies for the Stochastic k-Server Problem
• Faster Balanced Clusterings in High Dimension
• Biclustering and Boolean Matrix Factorization in Data Streams
• Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
• Relax, no need to round: integrality of clustering formulations
• Fair Clustering Under a Bounded Cost
• Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
• Facility Location Problem in Differential Privacy Model Revisited
• An approximation ratio for biclustering
• Greedy Selfish Network Creation
• Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search
• Deterministic k-Median Clustering in Near-Optimal Time
• Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
• Metric Distortion of Social Choice Rules: Lower Bounds and Fairness\n Properties

Related

• Simpler Analyses of Local Search Algorithms for Facility Location
• Local-Search based Approximation Algorithms for Mobile Facility Location Problems
• Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
• An Improved Local Search Algorithm for k-Median
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems