  In the Submodular Facility Location problem (SFL) we are given a collection
of $n$ clients and $m$ facilities in a metric space. A feasible solution
consists of an assignment of each client to some facility. For each client, one
has to pay the distance to the associated facility. Furthermore, for each
facility $f$ to which we assign the subset of clients $S^f$, one has to pay the
opening cost $g(S^f)$, where $g(\cdot)$ is a monotone submodular function with
$g(\emptyset)=0$.
  SFL is APX-hard since it includes the classical (metric uncapacitated)
Facility Location problem (with uniform facility costs) as a special case.
Svitkina and Tardos [SODA'06] gave the current-best $O(\log n)$ approximation
algorithm for SFL. The same authors pose the open problem whether SFL admits a
constant approximation and provide such an approximation for a very restricted
special case of the problem.
  We make some progress towards the solution of the above open problem by
presenting an $O(\log\log n)$ approximation. Our approach is rather flexible
and can be easily extended to generalizations and variants of SFL. In more
detail, we achieve the same approximation factor for the practically relevant
generalizations of SFL where the opening cost of each facility $f$ is of the
form $p_f+g(S^f)$ or $w_f\cdot g(S^f)$, where $p_f,w_f \geq 0$ are input
values.
  We also obtain an improved approximation algorithm for the related Universal
Stochastic Facility Location problem. In this problem one is given a classical
(metric) facility location instance and has to a priori assign each client to
some facility. Then a subset of active clients is sampled from some given
distribution, and one has to pay (a posteriori) only the connection and opening
costs induced by the active clients. The expected opening cost of each facility
$f$ can be modelled with a submodular function of the set of clients assigned
to $f$.
