A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem

We present a 1.488 approximation algorithm for the metric uncapacitated facility location (UFL) problem. Previously the best algorithm was due to Byrka [1]. By linearly combining two algorithms A1(gamma f) for gamma f approximate to 1.6774 and the (1.11,1.78)-approximation algorithm A2 proposed by Jain, Mahdian and Saberi [8], Byrka gave a 1.5 approximation algorithm for the UFL problem. We show that gamma f is randomly selected from some distribution, the approximation ratio can be improved to 1.488. Our algorithm cuts the gap with the 1.463 approximability lower bound by almost 1/3.