Improved approximation algorithms for solving the squared metric k-facility location problem

The squared metric k-facility location problem is a frequently encountered generalization of the k-means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44. 473 + ϵ, which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36. 342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric.

Authors

• Zhen Zhang
• Qilong Feng
• Junyu Huang
• Jianxin Wang

Keywords

• Approximation algorithm
• Squared metric k-facility location
• Lagrangian relaxation