An improved approximation algorithm for k-median problem using a new factor-revealing LP

2014/10/15 by Chenchen Wu, Wu, Chenchen, Dachuan Xu +5
Business, Management and Accounting · Decision Sciences · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Multi-Criteria Decision Making #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1410.4161

openalex publication_date 2014/10/15 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

The k-median problem is a well-known strongly NP-hard combinatorial optimization problem of both theoretical and practical significance. The previous best approximation ratio for this problem is 2.611+ε(Bryka et al. 2014) based on an (1, 1.95238219) bi-factor approximation algorithm for the classical facility location problem (FLP). This work offers an improved algorithm with an approximation ratio 2.592 +εbased on a new (1, 1.93910094) bi-factor approximation algorithm for the FLP.

Citations

• Local Search Heuristics for k-Median and Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

Related

• An improved approximation algorithm for k-Median
• A (2+ε)-Approximation Algorithm for Metric k-Median
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• Improved Bi-point Rounding Algorithms and a Golden Barrier for k-Median
• Constant-Factor Approximation for Ordered k-Median