Jarek
Byrka
Title:
n optimal bifactor approximation algorithm for the metric
uncapacitated facility location problem
Abstract:
We consider the metric uncapacitated facility location
problem(UFL).
In this paper we modify the $(1+2/e)$-approximation algorithm of Chudak
and Shmoys
to obtain a new (1.6774,1.3738)-approximation algorithm for the UFL
problem.
Our
linear programing rounding algorithm is the first one that touches the
approximability limit curve $(\gamma_f, 1+2e^{-\gamma_f})$
established by Jain et al.
As a consequence, we obtain the first optimal approximation algorithm
for instances dominated by connection costs.
Our new algorithm - when combined with a (1.11,1.7764)-approximation
algorithm proposed by Jain, Mahdian and Saberi,
and later analyzed by Mahdian, Ye and Zhang - gives a 1.5-approximation
algorithm for the metric UFL problem.
This algorithm improves over the previously best known
1.52-approximation algorithm by Mahdian, Ye and Zhang,
and it cuts the gap with the approximability lower bound by 1/3.
Additionally, we show that a single randomized clustering procedure
could be used
instead of the greedy clustering used in the algorithms of Shmoys et
al.,
Chudak et al., Sviridenko, and in the current paper.