  We obtain a 1.5-approximation algorithm for the metric uncapacitated facility
location problem (UFL), which improves on the previously best known
1.52-approximation algorithm by Mahdian, Ye and Zhang. Note, that the
approximability lower bound by Guha and Khuller is 1.463.
  An algorithm is a {\em ($\lambda_f$,$\lambda_c$)-approximation algorithm} if
the solution it produces has total cost at most $\lambda_f \cdot F^* +
\lambda_c \cdot C^*$, where $F^*$ and $C^*$ are the facility and the connection
cost of an optimal solution. Our new algorithm, which is a modification of the
$(1+2/e)$-approximation algorithm of Chudak and Shmoys, is a
(1.6774,1.3738)-approximation algorithm for the UFL problem and is the first
one that touches the approximability limit curve $(\gamma_f, 1+2e^{-\gamma_f})$
established by Jain, Mahdian and Saberi. As a consequence, we obtain the first
optimal approximation algorithm for instances dominated by connection costs.
When combined with a (1.11,1.7764)-approximation algorithm proposed by Jain et
al., and later analyzed by Mahdian et al., we obtain the overall approximation
guarantee of 1.5 for the metric UFL problem. We also describe how to use our
algorithm to improve the approximation ratio for the 3-level version of UFL.
