  The state of the art in approximation algorithms for facility location
problems are complicated combinations of various techniques. In particular, the
currently best 1.488-approximation algorithm for the uncapacitated facility
location (UFL) problem by Shi Li is presented as a result of a non-trivial
randomization of a certain scaling parameter in the LP-rounding algorithm by
Chudak and Shmoys combined with a primal-dual algorithm of Jain et al. In this
paper we first give a simple interpretation of this randomization process in
terms of solving an aux- iliary (factor revealing) LP. Then, armed with this
simple view point, Abstract. we exercise the randomization on a more
complicated algorithm for the k-level version of the problem with penalties in
which the planner has the option to pay a penalty instead of connecting chosen
clients, which results in an improved approximation algorithm.
