Improved combinatorial algorithms for the facility location and k-median problems

TLDR

The work builds on cost scaling and greedy improvement techniques. The authors aim to develop improved combinatorial approximation algorithms for facility location (both uncapacitated and capacitated) and k‑median problems. They employ greedy local search, cost scaling, greedy improvement, and a primal‑dual algorithm to achieve the approximations. The algorithms achieve a 2.414+ε approximation for uncapacitated facility location, a 1.853 ratio in near‑linear time, a 1.728 ratio when combined with LP methods, and a 4‑approximation for k‑median, while also providing improved bicriteria tradeoffs.

Abstract

We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2.414+/spl epsiv/ in O/spl tilde/(n/sup 2///spl epsiv/) This also yields a bicriteria approximation tradeoff of (1+/spl gamma/, 1+2//spl gamma/) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1.853 in O/spl tilde/(n/sup 3/) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1.728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O/spl tilde/(n/sup 3/) time.