We consider the uncapacitated facility location problem. There is a set of locations at which facilities can be built; a fixed cost $f_i$ is incurred if a facility is opened at location $i$. Furthermore, there is a set of demand locations to be serviced by the opened facilities; if the demand location $j$ is assigned to a facility at location $i$, there is an associated service cost of $c_{ij}$. We assume that the assignment costs $c_{ij}$ are symmetric and satisfy the triangle inequality. For this problem we obtain a $1.925$-approximation algorithm, improving on the recent $2.408$-approximation guarantee of Guha and Kuller. In contrast with Guha and Kuller's algorithms, we need the solution of just one linear program, thus providing a substantially faster algorithm.

Our algorithms are based on solving a classical linear programming relaxation for the problem. Our techniques use properties of optimal solutions to the linear program and randomized rounding, as well as a generalization of the techniques of Shmoys, Tardos \& Aardal.

Part of this work is in collaboration with David Shmoys.