Title: 
An Improved Approximation Algorithm for the Uncapacitated Facility Location Problem with Service Installation Costs

Authors:
Dachuan Xu
Department of Applied Mathematics
Beijing University of Technology
P.R. China


Shuzhong Zhang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin, Hong Kong

Abstract:
In this paper, we study the uncapacitated facility location
problem with service installation costs depending on the type of
service required. We propose a polynomial-time approximation
algorithm with approximation ratio $1.808$. The algorithm uses a
similar approach as in Byrka, based on linear programming
relaxation and randomized rounding. This new approximation ratio
improves the previous approximation ratio of $2.391$ of Shmoys,
Swamy, and Levi for the same problem.