
\section{Introduction}

In the {\sc Submodular Facility Location} problem (SFL), we are given a set $C$ of $n$ clients and set $F$ of $m$ facilities, with metric distances $d: (C\cup F)\times (C\cup F)\to \mathbb{R}_{\geq 0}$. Furthermore, we are given\footnote{As usual in this framework, we assume to have an oracle access to $g(\cdot)$: given $R\subseteq C$, we can obtain the value of $g(R)$ in polynomial time.} a monotone submodular (opening cost) function $g:2^{C}\to \mathbb{R}_{\geq 0}$ with $g(\emptyset)=0$. Notice that $g(\cdot)$ is non-negative. A feasible solution consists of an assignment $\varphi:C\to F$ of each client to some facility (we also say that $\varphi(c)$ \emph{serves} $c$). The opening cost of $f\in F$ in this solution is $g(\varphi^{-1}(f))$. The cost of the solution, that we wish to minimize, is the sum of the distances from each client to the corresponding facility plus the total opening cost of the facilities, in other words
$$
\cost(\varphi)=\sum_{c\in C}d(c,\varphi(c))+\sum_{f\in F}g(\varphi^{-1}(f)).
$$
SFL captures practical scenarios where the cost of opening a facility is a (non-linear, still ``tractable'') function of the set of served clients. As we will discuss, SFL is also closely related to certain stochastic optimization problems which recently attracted a lot of attention (see, e.g, \cite{AGLW17,GGLMSS13,GGLS08,GPRS11,IKMM04} and references therein). In particular, there are scenarios where one has to pay (a posteriori) the connection and opening costs related only to a random subset of \emph{activated} clients, and this naturally induces objective functions with submodular opening costs.

SFL is APX-hard since it includes the classical {\sc Facility Location} problem (with uniform facility costs) as a special case \cite{guha1999greedy}. Hence the best we can hope for, in terms of approximation algorithms, is a constant approximation. Finding such an approximation algorithm is explicitly posed as an open problem, e.g., by Svitkina and Tardos \cite{ST10}. The same authors present an $O(\log n)$ approximation for a generalization of SFL where each facility $f$ has a distinct submodular function $g_f(\cdot)$ (and this result is tight for this generalization due to a reduction from {\sc Set Cover} by Shmoys, Swamy and Levi \cite{SSL04}). Svitkina and Tardos also present a constant approximation for a rather restrictive (still practically motivated) special case of SFL where $g(\cdot)$ is induced by certain subtrees of a node-weighted tree over the clients.


\subsection{Our Results and Techniques}

We make some progress towards the resolution of the mentioned open problem by presenting an improved approximation algorithm for SFL.
\begin{theorem}\label{thr:main}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for SFL.
\end{theorem}
Our approach is surprisingly simple (modulo exploiting some non-trivial results in the literature). By standard reductions (see Section \ref{sec:preliminaries}) we can assume that $N=n+m$ is polynomial in $n$, hence it is sufficient to provide an $O(\log\log N)$ approximation. Our starting point is a natural (configuration) LP relaxation for the problem:
\begin{align}\label{eq:configuration-lp}\tag{Conf-LP}
        \min &\sum_{f \in F} \sum_{R \subseteq C} g(R) \cdot x_R^f
        + \sum_{c\in C} \sum_{f\in F} \sum_{R\ni c} d(c,f) \cdot x_R^f & \\
        %
        \text{s.t.} &
        \sum_{f\in F}\sum_{R\ni c} x_R^f= 1 &\forall c \in C;\nonumber \\
        & \sum_{R \subseteq C} x_R^f= 1 & \forall f \in F;\nonumber
        \\
        & x_R^f \geq 0 & \forall R\subseteq C,\ \forall f\in F.\nonumber
\end{align}
In an integral solution, we interpret $x^f_R=1$ as assigning exactly the set of clients $R$ to the facility $f$. Notice that we impose $\sum_{R \subseteq C} x_R^f = 1$. This is w.l.o.g. since $g(\emptyset)=0$ (intuitively, $x^f_\emptyset=1$ means that no client is assigned to $f$).
We can solve the above LP in polynomial time (see Section \ref{sec:omitted}).
\begin{lemma}\label{lem:solveConfLP}
  In $\poly(N)$ time one can find an optimal solution to \eqref{eq:configuration-lp} with $\poly(N)$ non-zero entries.
\end{lemma}

Given an optimal solution $\dot{x}=(\dot{x}^f_R)_{f\in F,R\subseteq C}$ to \eqref{eq:configuration-lp} of cost $\cost(\dot{x})$ as in Lemma \ref{lem:solveConfLP}, we proceed with two main stages. In the first stage (discussed in Section \ref{sec:reducingConnection}) we simply sample partial assignments of clients to facilities with the distribution induced by $\dot{x}$ for $\ln\ln N$ many times. This cost at most $\ln\ln N$ times the optimal LP cost in expectation, and leads to a partial solution that covers a random subset $C_1\subseteq C$ of clients.

In the second stage (discussed in Section \ref{sec:treeCase}) we take care of the remaining uncovered clients $C_2=C\setminus C_1$. Let us consider the restriction $\ddot{x}$ of $\dot{x}$ to $C_2$. The opening cost of $\ddot{x}$ might be as large as the opening cost of $\dot{x}$. However, in expectation, the connection cost of $\ddot{x}$ is only a $1/\ln N$ fraction of the connection cost of $\dot{x}$ (as we will show).

At this point, using the probabilistic tree embedding algorithm in \cite{FakcharoenpholRT04}, we embed the original metric $d$ into a (rooted) tree metric $d^T$ over a hierarchically well-separated tree (HST) $T$ (see Section \ref{sec:preliminaries} for the details). The opening cost of $\ddot{x}$ w.r.t.\ to the new tree instance does not change, while its connection cost grows by a factor at most $O(\log N)$ in expectation. Altogether we obtain a feasible fractional solution $\ddot{x}$ over the tree instance whose expected cost is at most $O(\cost(\dot{x}))$. Hence it is sufficient to develop an $O(\log\log N)$-approximate LP-rounding algorithm for the considered tree instance.

The next step is at the heart of our approach. Using the properties of HSTs and losing a constant factor in the approximation, we can further reduce our SFL tree instance to the following {\sc Descendant-Leaf Assignment} problem (DLA): the facilities are leaves of $T$ and the clients are arbitrary nodes of $T$. Each client $c$ must be served by a facility contained in the subtree $T_c$ rooted at $c$. The opening cost of each facility is given by $g(\cdot)$, and there are no connection costs at all. The latter problem is very similar to a problem recently studied by Bosman and Olver \cite{BO20} in the framework of {\sc Submodular Joint Replenishment} and {\sc Inventory Routing} problems. In particular, we can adapt their approach to achieve the desired $O(\log\log N)$ approximation for our DLA instance.

We remark that we do not know how to get an $O(1)$ approximation for SFL on trees (even on HSTs). Though such approximation would not imply an $O(1)$ approximation for SFL with our approach (due to the first stage), finding it seems to be a natural intermediate problem to address.


\subsection{Generalizations and Variants}

Our basic approach is rather flexible, and it can be applied to generalizations and variants of SFL. We next describe some other applications of our approach, and we expect to see a few more ones in the future. For example, we can handle the case where the opening cost of the facility $f$ is $g_f(S^f)=w_f\cdot g(S^f)$, where $w_f\geq 0$ is some input value: we call this the SFL {\sc with Multiplicative Opening Costs} problem ({\sc multSFL}).

\begin{theorem}\label{thr:mainMultiplicative}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for {\sc multSFL}.
\end{theorem}

Similarly, we can address the SFL {\sc with Additive Opening Costs} problem ({\sc addSFL}), where $g_f(S^f)=p_f+g(S^f)$ for $S^f\neq \emptyset$, $g_f(\emptyset)=0$, and $p_f\geq 0$ is some input value.
\begin{theorem}\label{thr:mainAdditive}
  There is a polynomial-time $O(\log\log n)$-approximation algorithm for {\sc addSFL}.
\end{theorem}
The above generalizations are discussed in \cref{sec:extensions}.
We remark that we do not know how to obtain an $O(\log\log n)$-approximation for the {\sc Affine} SFL case, where the opening costs are submodular functions of the form $g_f(S^f)=p_f+w_f\cdot g(S^f)$. Notice that this generalizes both {\sc addSFL} and {\sc multSFL}. This is left as an interesting and practically relevant open problem.

As mentioned earlier, SFL is closely related to stochastic variants of {\sc Facility Location}. In particular, our approach also extends to the following {\sc Universal Stochastic Facility Location} problem ({\sc univFL}). Here we are given clients $C$ and facilities $F$ with metric distances $d$ like in SFL, plus an opening cost $w_f$ for each $f\in F$. Furthermore, we have an oracle access to a probability distribution $\pi: 2^C\to \mathbb{R}_{\geq 0}$ specifying the probability $\pi(A)$ that a given subset of clients $A\subseteq C$ is activated. A feasible solution is an (universal) mapping $\varphi:C\to F$. The cost of $\varphi$ w.r.t.\ clients $A\subseteq C$ is $\cost_A(\varphi)=\sum_{c\in A}d(c,\varphi(c))+\sum_{f\in F:\varphi^{-1}(f)\cap A\neq \emptyset}w_f$. In words, this is the cost of connecting clients in $A$ to the corresponding facilities, plus the cost of opening the facilities that serve at least one client in $A$.
Our goal is to minimize $\mathbb{E}_{A\sim \pi}[\cost_A(\varphi)]$. The main motivation for \emph{universal} problems of this type is to allow a very quick (possibly distributed) reaction to requests that arrive over time. Let $\opt \colon C\to F$ minimize $\expected_{A\sim \pi}[\cost_A(\opt)]$, in other words $\opt$ is an optimal (universal) mapping. We say that an algorithm for {\sc univFL} is $\alpha$-approximate\footnote{In Section \ref{sec:related} we describe alternative ways to define the approximation ratio.} if it returns a universal mapping $\varphi$ satisfying $\mathbb{E}_{A\sim \pi}[\cost_{A}(\varphi)]\leq \alpha\cdot \mathbb{E}_{A\sim \pi}[\cost_A(\opt)]$.

Notice that the objective function of {\sc univFL} can be rewritten as
$$
  \sum_{c\in C}d(c,\varphi(c))\cdot \prob_{A\sim \pi}[\{c\}\cap A\neq \emptyset]+\sum_{f\in F}w_f\cdot \prob_{A\sim \pi}[\varphi^{-1}(f)\cap A\neq \emptyset].
$$
Hence {\sc univFL} is almost identical to SFL since $g(R) = \prob_{A\sim \pi}[R \cap A\neq \emptyset]$ is a monotone submodular function of $R$ which is $0$ for $R=\emptyset$. We can therefore adapt our techniques to achieve the following result (see \cref{sec:universal}). Let $\pi_{\min}\coloneqq \min_{c\in C}\{\prob_{A\sim \pi}[c\in A]\}$ be the smallest probability of any client to be activated. W.l.o.g. we will assume $\pi_{\min}>0$.
\begin{theorem}\label{thr:universalFL}
  There is a polynomial-time $O(\log\log \frac{n}{\pi_{\min}})$-approximation algorithm for the {\sc Universal Stochastic Facility Location} problem.
\end{theorem}
For a comparison, Adamczyk, Grandoni, Leonardi and W\l{}odarczyk \cite{AGLW17} obtain an $O(\log n)$ approximation which also holds for non-metric distances. In the case of metric distances, they obtain an $O(1)$ approximation but only in the \emph{independent activation case}, i.e., when the sampled set $A$ of active clients is obtained by independently sampling each client $c$ according to some input probability $\pi'(c)$ for $k$ times.


\subsection{Lower Bounds}

We believe that it is plausible that SFL admits a constant approximation. In particular, one might consider greedy algorithms. In \cref{app:lower-bound} we consider a natural set-cover type greedy algorithm {\tt GreedySFL} for SFL. The same algorithm gives a $1.861$-approximation when applied to the classical {\sc Facility Location} problem~\cite{JMMSV03}. We show that this algorithm does not produce $O(1)$ approximate solutions for SFL, and in fact, it is not better than our algorithm from Theorem~\ref{thr:main}.

\begin{theorem}\label{thm:lower-bound}
  {\tt GreedySFL} has an approximation ratio at least $\Omega(\log\log n)$.
\end{theorem}

The lower bound is based on the construction of a family of instances, parameterized by $\dime \in \mathbb{N}$, where the underlying metric is defined on a hypercube of dimension $\dime$.
We define $\dime \cdot 2^{\dime}$ clients and $O(\dime \cdot 2^{\dime})$ facilities.
The cost of a feasible solution is $2^{\dime}$, but the cost of the greedy algorithm is $\Theta(\log(\dime) \cdot 2^{\dime})$, hence the lower bound follows.
The main challenge in our construction is to define a submodular function $g(\cdot)$ on all subsets of clients.
We present a compact way of defining $g(\cdot)$: it is the expected value of a random process that depends on carefully designed distances (induced by edge weights) in the hypercube.


\subsection{Related Work}\label{sec:related}

In the {\sc (Metric Uncapacitated) Facility Location} problem (FL) we are given a set of clients and a set of facilities in a metric space $d$, where each facility has an opening cost $o_f$.
One has to select a subset of facilities $F'\subseteq F$ and assign each client $c$ to the closest facility $F'(c)$ in $F'$ so as to minimize $
\sum_{c\in C}d(c,F'(c))+\sum_{f\in F'}o_f$.
FL is a special case of both {\sc addSFL} and {\sc multSFL} (and of SFL in the case of uniform opening costs).
FL is among the best-studied problems in the literature from the point of view of approximation algorithms (see, e.g., \cite{CG05,MYZ06,STA97}). It is known to be APX-hard~\cite{guha1999greedy} and the current best-known 1.488-approximation algorithm~\cite{li20131} is a randomized combination of the greedy JMS algorithm~\cite{JMMSV03} with an LP-rounding algorithm from~\cite{byrka2010optimal}. Lagrangian-multiplier preserving algorithms for FL are at the heart of several approximation algorithms for fundamental clustering problems, including {\sc $k$-Median} \cite{ANSW20,BPRST17,CEMN22,CGLS23,GPST23,JMMSV03,JV01,LS16} and {\sc $k$-Means} \cite{ANSW20,CEMN22,GORSV22}.

Various variants of FL were studied in the literature and for most of them (at least with metric connection costs) a constant approximation was eventually discovered. A notable example is the {\sc Capacitated Facility Location} problem in which the number of clients that can be served from a facility is restricted by a location-specific bound. A local-search-based constant approximation for the latter problem is given in \cite{zhang2005multiexchange} (see also \cite{an2017lp} for a more recent LP-based result). SFL is one of the most natural generalizations of (metric) FL where a constant approximation is still not known.

Grandoni, Gupta, Leonardi, Miettinen, Sankowski, and Singh \cite{GGLMSS13}, among other universal stochastic problems, studied {\sc univFL} in the independent activation case. However, they compare the cost of their solution with $\expected_{A\sim \pi}[\cost_A(\opt(A))]$, where $\opt(A)$ is the optimal facility location solution restricted to clients $A$ (while we compare with $\expected_{A\sim \pi}[\cost_A(\opt)]$). For this setting they obtain a $O(\log n)$ approximation, which also holds for non-metric connection costs.

Gupta, P{\'a}l, Ravi, and Sinha \cite{GPRS11} consider a 2-stage stochastic version of FL. Here in a first stage, one buys some facilities, then a subset of active clients is sampled from a given distribution. Finally, one can buy some more facilities, however at an opening cost which is increased by a multiplicative \emph{inflation factor} $\sigma$. For this setting they present a constant approximation.

Universal stochastic problems have a natural online stochastic counterpart. For example, in the {\sc Online Stochastic Facility Location} problem clients are sampled one by one, and when client $c$ is sampled one has to connect $c$ to an already open facility or open a new facility $f$ and connect $c$ to $f$. Garg, Gupta, Leonardi and Sankowski \cite{GGLS08} consider this problem in the independent activation case, i.e. when the next client to be served is sampled from a probability distribution $\pi:C\to \mathbb{R}_{\geq 0}$. For this setting, they present an $O(1)$ approximation. Meyerson \cite{Meyerson01} studied a variant of the problem where an adversary chooses the set of input clients, and then a random permutation of them is presented in input (\emph{random order model}).


\subsection{Preliminaries and Notation}\label{sec:preliminaries}

We use $\ln$ and $\log$ for the logarithm with base 2 and $\ln$ for the natural logarithm.
Define $X = C \cup F$, and $N=|X|=|C \cup F|$. Given a metric $d$ over $X$, we let $d_{\min}$ be the smallest non-zero distance and $d_{\max}$ be the largest distance (that we assume to be positive w.l.o.g). We use $g(c)$ as a shortcut for $g(\{c\})$.

We sometimes express a feasible solution to SFL in the form $S=(S^f)_{f\in F}$, where $S^f\subseteq C$ specifies the clients $\varphi^{-1}(f)$ assigned to $f$. Notice that for each $c\in C$ there is precisely one $f\in F$ with $c\in S^f$. We define a \emph{partial assignment} as $S=(S^f)_{f\in F}$, where $S^f\subseteq C$. We say that $S$ covers the clients $C'=\cup_{f\in F}S^f\subseteq C$. Notice that, for technical reasons, in a partial assignment we allow $S^f\cap S^{f'}\neq \emptyset$ for two distinct $f,f'\in F$ (i.e. we allow to simultaneously assign a client to more than one facility). The cost of a (partial) assignment $S$ of the above type is defined as
$
  \cost(S)\coloneqq \conn(S)+\open(S),
$
where $\conn(S)\coloneqq \sum_{f\in F}\sum_{c\in S^f}d(c,f)$ is the connection cost of $S$ and $\open(S)\coloneqq \sum_{f\in F}g(S^f)$ is the opening cost of $S$. Given a (possibly infeasible) fractional solution $x$ for \eqref{eq:configuration-lp}, we analogously define $\cost(x)=\conn(x)+\open(x)$, where $\conn(x)=\sum_{c\in C} \sum_{f\in F} \sum_{R\ni c} d(c,f) \cdot x_R^f$, and $\open(x)=\sum_{f \in F} \sum_{R \subseteq C} g(R) \cdot x_R^f$.

It is convenient to define the merge $S=S_1+S_2$ of two partial assignments $S_1$ and $S_2$ naturally as follows: (1) for each facility $f\in F$, we initially set $S^f\coloneqq S^f_1\cup S^f_2$; (2) while there exist two distinct facilities $f$ and $f'$ with $S^{f}\cap S^{f'}\neq \emptyset$, replace $S^{f'}$ with $S^{f'}\setminus S^f$ (intuitively this second step guarantees that each client is assigned to no more than one facility). We observe that merging two partial assignments cannot increase the total cost.

\begin{lemma}\label{lem:merge}
  For any two partial assignments $S_1$ and $S_2$, $\cost(S_1+S_2)\leq \cost(S_1)+\cost(S_2)$.
\end{lemma}
\begin{proof}
Let $S=S_1+S_2$, and $S'$ be the intermediate value of $S$ obtained by executing only step (1) of the merge operation. One has $\conn(S')=\conn(S_1)+\conn(S_2)$. Furthermore, by the submodularity (hence subadditivity) of $g(\cdot)$, $\open(S')\leq \open(S_1)+\open(S_2)$.
Clearly $\conn(S)\leq \conn(S')$, and the monotonicity of $g(\cdot)$ implies that $\open(S)\leq \open(S')$. The claim follows.
\end{proof}
We will exploit the following fairly standard reductions (proofs in Section \ref{sec:omitted}), thanks to which in the following it will be sufficient to obtain an $O(\log\log N)$ approximation for SFL. In order to distinguish between distinct instances $J$ of the problem, we use $\cost_J(\varphi)$ to denote the cost of $\varphi$ w.r.t.\ $J$ and define similarly $\open_J(\varphi)$ etc.
\begin{lemma}\label{lem:reduceNumberFacilities}
  There is a $3$-approximate reduction from SFL to the special case where $m=n$.
\end{lemma}

\begin{lemma}\label{lem:reduceDistances}
  For any constant $\varepsilon>0$, There is a $(1+4\varepsilon)$-approximate reduction from SFL to the special case where the metric $d$ satisfies $d_{\min}=2$ and $d_{\max}\leq \frac{2nN}{\varepsilon}$.
\end{lemma}

One of the key tools that we use is the notion of probabilistic tree embedding, which we use to map the input metric into a metric on a \emph{hierarchically well-separated tree} (HST) while stretching the distances by a small enough factor. We recall that an HST is an edge weighted rooted tree where all the leaves are at the same distance from the root $r$. Furthermore, on every path from a leaf to $r$ the edge weights are $1,2,4,\dots$ In particular, edges at the same level have the same weight. We will use the following construction\footnote{We slightly and trivially extend their claim to consider nodes at distance $0$.} by Fakcharoenphol, Rao and Talwar~\cite{FakcharoenpholRT04}.

\begin{theorem}[FRT metric tree embedding~\cite{FakcharoenpholRT04}]\label{thm:frt-tree-embedding}
    For any finite metric space $(M,d)$ with $d_{\min}>1$, there exists a randomized polynomial-time algorithm returning an HST $T$ such that:
    \begin{enumerate}\itemsep0pt
        \item Every $a\in M$ is mapped to some leaf $v(a)$ of $T$ (with elements at distance zero being mapped to the same leaf);
        \item Let $d^T(v(a),v(b))$ be the length of the path between the leaves $v(a)$ and $v(b)$ of $T$. Then $d^T\left(v(a),v(b)\right) \geq d(a,b)$ and $\expected\left[d^T(v(a),v(b))\right] \leq 8 \log |M| \cdot d(a,b)$;
        \item $T$ has depth $O(\log d_{\max})$.
    \end{enumerate}
\end{theorem}

For a given set $C$, let $h\colon 2^C\to {\mathbb R}$ be a
monotone submodular function with $h(\emptyset)=0$. The \emph{Lov\'{a}sz extension} $\hat{h}\colon [0,1]^C \rightarrow {\mathbb R}$ of $h(\cdot)$ is defined as
\begin{equation}\label{eq:lovasz-extension}
  \hat h(y) \coloneqq \min\Big\{\;\sum_{R \subseteq C}h(R)\mu_R:\ \sum_{R\subseteq C}\sum_{R \ni c}\mu_R = y_c \ \forall c\in C,\ \sum_{R \subseteq C} \mu_R=1,\ \mu\geq0 \;\Big\}.
\end{equation}
The function $\hat h(\cdot)$ is convex. We remark that $\hat h(y)$ can be alternatively defined as
\begin{equation}\label{eq:lovasz-extension-bis}
    \hat h(y) \coloneqq
        \sum_{k=1}^{n-1} h\left(\{c_1, \dots, c_k\}\right)
        (y_{c_k} - y_{c_{k+1}}) + h(C) y_{c_{n}}
\end{equation}
where the components of $y$ are sorted in decreasing order, i.e. $y_{c_1} \geq y_{c_2} \geq \dots \geq y_{c_{n}}$ \cite[Section~6.3]{fujishige2005submodular}.
By the monotonicity of $h(\cdot)$, $\hat h(\cdot)$ is also non-decreasing in the sense that $\hat h(y) \geq \hat h(y')$ if $y\geq y'$.


\section{Reducing the Connection Cost}\label{sec:reducingConnection}

In this section, we show how to compute a random partial assignment $S_1=(S_1^f)_{f\in F}$ covering a random subset of clients $C_1\coloneqq \cup_{f\in F}S_1^f\subseteq C$ with the following high-level properties: the expected cost of $S_1$ is ``small enough'' and (2) each client belongs to $C_1$ with ``large enough'' probability. In the next section, we will describe a different partial assignment $S_2=(S_2^f)_{f\in F}$, again of small enough cost, covering the remaining clients $C_2\coloneqq C\setminus C_1$. By merging these two partial assignments we obtain a feasible solution for the input problem of small enough total cost.

Let $\dot{x}$ be an optimal solution to \eqref{eq:configuration-lp} with at most $\poly(N)$ non-zero entries that can be computed via Lemma \ref{lem:solveConfLP}. The basic idea behind the next lemma is fairly standard: we sample partial assignments according to the distribution induced by $\dot{x}$ for $\ln\ln N$ times, and merge them together.

\begin{lemma}\label{lem:sampling}
  In polynomial time one can compute a random partial assignment $S_1$ covering a random subset of clients $C_1$ such that: (1) $\expected\left[\cost(S_1)\right] \leq \ln\ln (N) \cdot \cost(\dot{x})$ and (2) For each $c\in C$, $\prob[c\in C_1]\geq 1-\frac{1}{\ln N}$.
\end{lemma}
\begin{proof}
For $i \in \{1,2,\dots,\ln\ln N\}$ and for every $R\subseteq C$, we define a partial assignment $S(i,R)$ by setting $S^f(i,R)=R$ independently with probability $\dot{x}_{R}^f$ and $S^f(i,R)=\emptyset$ otherwise. Let $S_1=\sum_{i=1}^{\ln\ln N}\sum_{R\subseteq C}S(i,R)$ be obtained by merging all these solutions, and let $C_1=\cup_{f\in F}S_1^f$. Observe that
$$
  \prob[c\notin C_1]=\prod_{f\in F}\prod_{R\ni c}(1-\dot{x}_R^f)^{\ln\ln N}\leq e^{-\ln\ln N\sum_{f\in F}\sum_{R\ni c}\dot{x}_S^f}\leq e^{-\ln\ln N}=\frac{1}{\ln N}.
$$
Furthermore, by \cref{lem:merge}, $\expected[\cost(S_1)]$ is upper-bounded by
$$
\sum_{i=1}^{\ln\ln N}\sum_{R\subseteq C}\expected[\cost(S(i,R))]=\ln\ln N\cdot \sum_{f\in F,R\subseteq C}\dot{x}^f_{R}\cdot \bigg(g(R)+\sum_{c\in R}d(c,f)\bigg)= \ln\ln N\cdot \cost(\dot{x}).\qedhere
$$
\end{proof}
Consider the partial assignment $S_1$ covering the random subset of clients $C_1$ as in the previous lemma. Let $C_2\coloneqq C\setminus C_2$ be the remaining (uncovered) clients.
Let also $\ddot{x}$ be $\dot{x}$ restricted to $C_2$, i.e. $\ddot x_R^f = \sum_{R' \subseteq C_1} \dot x_{R \cup R'}^f$ for $R \subseteq C_2$ and $f\in F$. The following lemma upper bounds the expected opening and connection cost of $\ddot{x}$.

\begin{lemma}\label{lem:costResidualClients}
  One has $\open(\ddot{x})\leq \open(\dot{x})$ and $\expected[\conn(\ddot{x})]\leq \frac{1}{\ln N}\conn(\dot{x})$.
\end{lemma}
\begin{proof}
    We have $\open(\ddot{x})\leq \open(\dot{x})$ by the monotonicity of $g(\cdot)$. For the connection cost, notice that the probability of a client $c$ being in $C_2$ is at most $1/\ln N$, and only in that case one has to pay the associated connection cost. Thus by linearity of expectation, the expected connection cost of $\ddot{x}$ is at most $\conn(\dot{x})/\ln N$. The claim follows.
\end{proof}
Notice that $\ddot{x}$ is a feasible fractional solution for~\eqref{eq:configuration-lp} limited to $C_2$.
In the following section, we show how to randomly round $\ddot{x}$ to a partial assignment $S_2$ which covers $C_2$ at expected cost $O(\log\log N) \cdot \cost(\ddot{x})$. It will then follow that $S_1+S_2$ is a feasible $O(\log\log N)$-approximate solution to the input SFL instance.


\section{Approximating SFL on an HST}\label{sec:treeCase}

We say that an instance $(C\cup F,d^T,g(\cdot))$ of SFL is of \emph{HST-type} if the metric $d^T$ is an HST metric over a tree $T$ of the type guaranteed by Lemma \ref{lem:sampling}. We remark that we allow multiple clients $C(v)$ and facilities $F(v)$ to be colocated at each leaf $v$ of $T$. In this section we will describe an $O(\log\log N)$-approximate LP-rounding algorithm for the considered instances w.r.t.\ \eqref{eq:configuration-lp}.
\begin{lemma}\label{lem:treeLProunding}
  Given a feasible fractional solution $x$ to \eqref{eq:configuration-lp} for an HST-type SFL instance, in polynomial time one can compute a feasible (integral) solution for the same instance with cost at most $O(\log\log N)\cdot \cost(x)$.
\end{lemma}
Theorem \ref{thr:main} directly follows.
\begin{proof}[Proof of Theorem \ref{thr:main}]
By Lemma \ref{lem:reduceNumberFacilities} it is sufficient to describe an $O(\log\log N)$-approximation. Furthermore by Lemma \ref{lem:reduceDistances}, we can assume that $d_{\min}=2$ and $d_{\max}\leq \frac{2nN}{\varepsilon}$.

By applying the construction of Section \ref{sec:reducingConnection} we compute a random partial assignment $S_1=(S^f_1)_{f\in F}$ covering the clients $C_1=\cup_{f\in F}S^f_1$ with expected cost at most $O(\log\log N)\cdot \cost(\dot{x})$, where $\dot{x}$ is an optimal solution to \eqref{eq:configuration-lp}. Furthermore, by Lemma \ref{lem:costResidualClients}, we obtain a feasible solution $\ddot{x}$ to \eqref{eq:configuration-lp} restricted to clients $C_2\coloneqq C\setminus C_1$ which satisfies $\open(\ddot{x})\leq \open(\dot{x})$ and $\expected[\conn(\ddot{x})]\leq \frac{1}{\ln N}\conn(\dot{x})$. By applying the probabilistic tree embedding from Theorem \ref{thm:frt-tree-embedding} to the metric $(C_2\cup F,d)$, we obtain an HST-type SFL instance $(C_2\cup F,d^T,g(\cdot))$ where the tree has depth $D=O(\log d_{\max})=O(\log N)$. Observe that $\ddot{x}$ is a feasible fractional solution for \eqref{eq:configuration-lp} restricted to $C_2$ on the HST-type instance. Furthermore, let $\conn_{T}(\ddot{x})$ denote the connection cost of $\ddot{x}$ w.r.t.\ the HST-type instance, and define similarly $\open_{T}(\ddot{x})$ and $\cost_{T}(\ddot{x})$. Then one has
$$
  \expected[\cost_{T}(\ddot{x})]=\open(\ddot{x})+\expected[\conn_{T}(\ddot{x})]\leq \open(\dot{x})+O(\log N)\cdot\expected[\conn(\ddot{x})] \leq O(\cost(\dot{x})).
$$
By applying the LP-rounding algorithm from Lemma \ref{lem:treeLProunding} to $\ddot{x}$ one obtains a partial assignment $(S^f_2)_{f\in F}$ covering the clients $C_2$ of cost at most $O(\log\log N)\cost(\dot{x})$. The same solution has no larger cost in the original problem (on a non-tree metric). Altogether $S_1+S_2$ is a feasible solution to the input SFL problem of expected cost at most $O(\log\log N)\cdot \cost(\dot{x})\leq O(\log\log N)\cdot\cost(\opt)$.
\end{proof}

In the rest of this section, we prove Lemma \ref{lem:treeLProunding}. To this aim, we will first present a reduction to a different problem that we call the {\sc Descendent-Leaf Assignment} problem (DLA) (see Section \ref{sec:reductionDLA}). Then, we will present a good-enough approximation algorithm for DLA (see Section \ref{sec:approximationDLA}).


\subsection{A Reduction to DLA}\label{sec:reductionDLA}

In the {\sc Descendent-Leaf Assignment} problem (DLA) we are given a rooted tree $\tilde{T}$ with depth $D$, a set of facilities $\tilde{F}$ and a set of clients $\tilde{C}$. Each $x\in \tilde{F}\cup \tilde{C}$ is mapped into some node $v(x)$ of $\tilde{T}$, with the restriction that facilities are mapped into leaves of $\tilde{T}$.
By $\tilde{F}_c$ we denote the facilities which are assigned to nodes that are descendants of $v(c)$ in $T$ ($v(c)$ included if it is a leaf).
A feasible solution consists of an assignment $\tilde{\varphi}:\tilde{C}\to \tilde{F}$ of each $c\in \tilde{C}$ to some $f\in \tilde{F}_c$. The cost of this solution is $\sum_{f\in \tilde{F}}h(\tilde{\varphi}^{-1}(f))$, where $h(\cdot)$ is a monotone submodular function over $\tilde{C}$ with $h(\emptyset)=0$. Similarly to SFL, we also express a feasible solution as $S=(S^f)_{f\in \tilde{F}}$, where $S^f=\tilde{\varphi}^{-1}(f)$, and let $\cost_{\DLA}(S)=\sum_{f\in \tilde{F}}h(S^f)$ be the associated cost. We define a convex-programming (CP) relaxation for DLA as follows:
\begin{align*}\label{eq:DLA-LP}\tag{DLA-CP}
        \min & \sum_{f \in \tilde{F}} \hat h(z^f) \\
        \text{s.t.} \quad
        &\sum_{f \in \tilde{F}_c} z_c^f = 1 \quad \forall c\in \tilde{C}. \\
        & z_c^f \geq 0 \quad \forall c\in \tilde{C},\ \forall f \in \tilde{F}.
\end{align*}
In a $0$-$1$ integral solution we interpret $z^f_c=1$ as $c$ being assigned to $f$. Recall that $\hat h(\cdot)$ is convex, which makes \eqref{eq:DLA-LP} a convex program. We also notice that each feasible assignment $S=(S^f)_{f\in \tilde{F}}$ corresponds to a feasible integral solution $z=(z^f)_{f\in \tilde{F}}$ to \eqref{eq:DLA-LP} with $\cost_{\DLA}(S)=\cost_{\DLA}(z)\coloneqq \sum_{f\in \tilde{F}}\hat{h}(z^f)$ and vice versa. Hence indeed \eqref{eq:DLA-LP} is a CP-relaxation of DLA.

The next lemma provides the claimed reduction from SFL on HST-type instances to DLA.
\begin{lemma}\label{lem:DLAreduction}
  Given a polynomial-time $O(\log D )$-approximate CP-rounding algorithm for DLA w.r.t.\ \eqref{eq:DLA-LP}, where $D$ is the depth of the tree, there is polynomial-time $O(\log\log N)$-approximate LP-rounding algorithm for SFL on HST-type instances with tree-depth $O(\log N)$ w.r.t.\ \eqref{eq:configuration-lp}.
\end{lemma}
\begin{proof}
Let $(C\cup F,d^T,g(\cdot))$ be the considered instance of SFL over an HST $T$, and $x$ be an input feasible fractional solution to \eqref{eq:configuration-lp} for this instance.

We build an instance of DLA as follows.
First, let $y^f_c\coloneqq \sum_{R\subseteq C:c\in R}x^f_R$: intuitively this is the fractional amount by which $c$ is assigned to $f$ in $x$. We set $h(\cdot)=g(\cdot)$ and $\tilde{T}=T$. Notice that $D=O(\log N)$. We set $\tilde{F}=F$ and map each $f\in \tilde{F}$ to the corresponding leaf of $T$ containing $f$. We also set $\tilde{C}=C$, and map each $c\in \tilde{C}$ to a node $v(c)$ as follows. Let $T_v$ be the subtree rooted at $v$ (containing $v$ and all its descendants) and $F_v$ be the facilities located in the leaves of $T_v$. Let also $\ell(c)$ be the leaf of $T$ containing $c$ in the mapping associated with $T$. We define $v(c)$ as the lowest ancestor of $\ell(c)$ such that $\sum_{f\in F_{v(c)}}y_c^f\geq 1/2$. Notice that $v(c)=\ell(c)$ is possible (in which case there is at least one facility $f$ colocated with $c$ at $l(c)$).

We next define a feasible fractional solution $z$ for \eqref{eq:DLA-LP} w.r.t this DLA instance as follows.
For each $c\in \tilde{C}$ we set $z^f_{v(c)}=y^f_c/(\sum_{f'\in F_{v(c)}}y^{f'}_c)$ if $f\in F_{v(c)}$, and otherwise $z^f_{v(c)}=0$. Let $\tilde{\varphi}$ be a solution to the DLA instance obtained with the CP-rounding algorithm in the claim w.r.t.\ $z$. We obtain a feasible solution $\varphi$ for the input instance by simply setting $\varphi(c)= \tilde{\varphi}(c)$.

It remains to analyze the cost of $\varphi$.
Define $\bar{z}^f_{v(c)}=y^f_c/(\sum_{f'\in F_{v(c)}}y^{f'}_c)$ for all $f\in F$. Notice that $\bar{z}\geq z$. By the definition of $\hat h(\cdot)$ and its monotonicity, $\hat{h}(z^f)\leq \hat{h}(\bar{z}^f)=\hat{h}(y^f/(\sum_{f'\in F_{v(c)}}y^{f'}_c))\leq 2\hat{h}(y^f)=2\hat{g}(y^f)$.
Notice that by plugging in $x_R^f$ for $\mu_R$ in the set in \eqref{eq:lovasz-extension} and by how $y$ is defined w.r.t.\ $x$ above, we get $\hat g(y^f) \leq \sum_{R \subseteq C}g(R)\cdot x_R^f$ and in particular $\sum_{f\in F}\hat g(y^f) \leq \open(x)$. Thus, we have $\cost_{\DLA}(z)\leq 2\open(x)$ and
\begin{equation}\label{eq:dlareduction-openingcosts}
  \open(\varphi)=\cost_{\DLA}(\tilde{\varphi})=O(\log D)\cdot\cost_{\DLA}(z)\leq O(\log \log N)\cdot 2\open(x).
\end{equation}
Consider next the connection cost. For each client $c\in C$, let $\Delta$ be the weight of the edge between $v(c)$ and its children in $T$. Observe that the distance between $v(c)$ and the leaves in $T_{v(c)}$ is exactly $2\Delta-1$.
Furthermore, both $c$ and $\varphi(c)$ are located in the leaves of $T_{v(c)}$ in the HST mapping. Hence
$
  d^T(c,\varphi(c))\leq 2(2\Delta-1).
$
We next compare the latter cost with the connection cost associated with $c$ in $x$, namely $\sum_{f\in F}d(c,f)y^f_c$. Let $\alpha=\sum_{f\in F_{v(c)}}y^f_c\geq \frac{1}{2}$. Suppose first that $\alpha\leq \frac{5}{6}$. Notice that for each $f\in F\setminus F_{v(c)}$, if any, the $f$-$c$ path in $T$ uses the edge, of weight $2\Delta$, between $v(c)$ and its parent. In particular, all such paths have length at least $2(4\Delta-1)$. Furthermore, $\sum_{f\in F\setminus F_{v(c)}}y^f_c=1-\alpha\geq \frac{1}{6}$. Thus
$$
  \sum_{f\in F}d(c,f)y^f_c\geq \sum_{f\in F\setminus F_{v(c)}}d(c,f)y^f_c\geq \frac{1}{6}2(4\Delta-1)\geq \frac{2}{3}(2\Delta-1).
$$
Consider next the complementary case where $\alpha\geq \frac{5}{6}$. Let $w(c)$ be the child of $v(c)$ along the $v(c)$-$c$ path in $T$. By the definition of $v(c)$, it must be the case that $\sum_{f\in F_{w(c)}}y^f_c< \frac{1}{2}$, and consequently $\sum_{f\in F_{v(c)}\setminus F_{w(c)}}y^f_c\geq \frac{1}{3}$. For each $f\in F_{v(c)}\setminus F_{w(c)}$, the $f$-$c$ path in $T$ has length exactly $2(2\Delta-1)$. Thus
$$
  \sum_{f\in F}d(c,f)y^f_c\geq \sum_{f\in F_{v(c)}\setminus F_{w(c)}}d(c,f)y^f_c\geq \frac{2}{3}(2\Delta-1).
$$
In both cases the connection cost of $c$ in $\varphi$ is at most $3$ times its connection cost in $x$. We conclude that $\conn(\varphi)\leq 3\conn(x)$. Altogether
$
  \cost(\varphi)\leq 3\conn(x)+O(\log\log N)\cdot 2\open(x)\leq O(\log\log N)\cdot \cost(x).
$
\end{proof}


\subsection{An Approximation Algorithm for DLA}\label{sec:approximationDLA}

In this section, we present a CP-rounding algorithm for DLA. Lemma \ref{lem:treeLProunding} follows by chaining Lemmas \ref{lem:DLAreduction} and \ref{lem:DLArounding}.
\begin{lemma}\label{lem:DLArounding}
  Given a feasible fractional solution $z$ to \eqref{eq:DLA-LP} on an instance of DLA with tree-depth $D$, in polynomial time one can compute a feasible (integral) solution to the same instance of cost at most $O(\log D)\cdot \cost_{\DLA}(z)$.
\end{lemma}
The CP-rounding algorithm from \cref{lem:DLArounding} is essentially the algorithm by Bosman and Olver \cite{BO20} with minor modifications that we introduced to simplify our correctness analysis. Also, the analysis of its approximation ratio is essentially identical to \cite{BO20}, but we reproduce it for the sake of completeness. In particular, we will exploit the following definitions and lemma from \cite{BO20}. Let $h:2^{\tilde{C}}\to \mathbb{R}_{\geq 0}$ be a monotone submodular function with $h(\emptyset)=0$. For a given $f\in \tilde{F}$ and a (possibly infeasible) solution $z$ to \eqref{eq:DLA-LP}, let $L_\theta(z^f)\coloneqq \{c\in \tilde{C}: z^f_c\geq\theta\}$ be the set of clients that are served fractionally by at least some value $\theta$ by $f$. Let also $z^{f|\theta}$ be obtained from $z^f$ by rounding down to $\theta$ the values larger than $\theta$, i.e. $z_c^{f|\theta}\coloneqq \min\{z^f_c,\theta\}$ for each $c\in \tilde{C}$. Given $\theta\in [0,1]$ and $z^f\in [0, 1]^{\tilde{C}}$, we say that the set $L_\theta(z^f)$ is $\alpha$-supported (w.r.t.\ $h$) if
$
  \hat h(z^f) - \hat h(z^{f|\theta}) \geq \alpha h(L_\theta(z^f)).
$
\begin{lemma}[{\cite[Lemma 5.2]{BO20}}]\label{lem:BO20}
  Given $z^f\in [0, 1]^{\tilde{C}}$ and $\alpha\in (0, 1]$, at least one of the following holds:
  (1) there exists $\theta\in [0, 1]$, which can be computed in polynomial time, such that $L_\theta(z^f)$ is $\frac{\alpha}{32}$-supported; (2) $2^{1/\alpha}h(L_1(z^f))\leq\hat h(z^f)$.
\end{lemma}

Our algorithm is Algorithm~\ref{alg:tree} in the figure. Recall that $\tilde{T}_v$ is the subtree rooted at node $v$, where $\tilde{T}_v$ includes $v$ and all its descendants. Furthermore, $\tilde{F}_v$ is the set of facilities mapped into the leaves of $\tilde{T}_v$. As usual the level of a node is its hop-distance from the root.
\begin{algorithm}
    \caption{}
    \footnotesize
    \textbf{Input:} Feasible solution $z$ to \eqref{eq:DLA-LP}
    \begin{algorithmic}[1]
        \State $S^f\gets \emptyset$ for all $f\in F$
        \For{$i=0,\dots, D$}
            \State For every node $v$ at level $D-i$, choose an arbitrary $f_v\in \tilde{F}_v$ and set $z^{f_v}\gets\sum_{f'\in \tilde{F}_v}z^{f'}$ and $z^{f'}\gets 0$

            for all $f'\in \tilde{F}_v\setminus \{f_v\}$\label{alg:merging}
            \If{there exists $\theta\in [0,1]$ such that $L_\theta(z^{f_v})$ is $\frac{1}{32\log (D+1)}$-supported}\label{alg:condition}
                \State For an arbitrary such $\theta$, set $S^{f_v}\gets S^{f_v}\cup L_\theta(z^{f_v})$ and $z^{f_v}_c\gets 0$ for all $c\in L_\theta(z^{f_v})$ \label{alg:choose-theta}
            \Else
                \State Set $S^{f_v}\gets S^{f_v}\cup L_1(z^{f_v})$ and $z^{f_v}_c\gets 0$ for all $c\in L_1(z^{f_v})$\label{alg:buying-integrals}
            \EndIf
        \EndFor
        \State For every $c\in \tilde{C}$ choose $f\in\tilde{F}_c$ such that $c\in S^{f}$ and set $S^{f'}\gets S^{f'}\setminus\{c\}$ for all $f'\in \tilde{F}\setminus\{f\}$ \label{alg:pruning}
        \State \textbf{return} $(S^f)_{f\in \tilde{F}}$
    \end{algorithmic}
    \label{alg:tree}
\end{algorithm}

Clearly Algorithm~\ref{alg:tree} runs in polynomial time.
The next two lemmas analyze the correctness and the approximation ratio of Algorithm \ref{alg:tree}, hence proving Lemma \ref{lem:DLArounding}.
\begin{lemma}\label{lem:DLAcorrectness}
  Algorithm \ref{alg:tree} computes a feasible DLA solution.
\end{lemma}
\begin{proof}
Consider a given client $c\in \tilde{C}$ such that $v(c)$ is at level $D-i$ in $\tilde{T}$. Let us show that the following invariant holds at the beginning of each iteration $j\leq i$: either $\sum_{f\in \tilde{F}_c}z^f_c=1$ or $c\in S^f$ for some $f\in \tilde{F}_c$. The invariant trivially holds for $j=0$. Assume that it holds up to the beginning of iteration $j<i$, and consider what happens during that iteration. Notice that for every node $v$ at level $D-j>D-i$, we either have that every $f \in\tilde{F}_v$ is a descendant of $v(c)$ or every $f \in\tilde{F}_v$ is not in $\tilde{F}_c$. Therefore, in Step \eqref{alg:merging} the value of $\sum_{f\in \tilde{F}_c}z^f_c$ does not change. In more detail, it remains $1$ by inductive hypothesis. The same value can decrease in Steps \eqref{alg:choose-theta} or \eqref{alg:buying-integrals}, however, this can only happen if $c$ is added to $S^{f_v}$ for some $f_v\in \tilde{F}_c$. Thus the invariant holds at the end of the $j$-th iteration, hence at the beginning of the next iteration $j+1$.

Due to the invariant, during the iteration $i$, when one considers the node $v=v(c)$, one has that either $c$ already belongs to some $S^f$ with $f\in \tilde{F}_c$, or $\sum_{f\in \tilde{F}_c}z^f_c=1$. In the latter case, after Step~\eqref{alg:merging}, $z_c^{f_{v}}=1$ where $f_{v}\in \tilde{F}_c$, so $c$ belongs to every set $L_\theta(z^{f_{v}})$ with $\theta\in [0,1]$. As a consequence, $c$ is added to $S^{f_v}$ either in Step \eqref{alg:choose-theta} or in Step \eqref{alg:buying-integrals}.

It might happen that a client $c$ is assigned \emph{also} to a facility not in $\tilde{F}_c$. Step~\eqref{alg:pruning} guarantees that the final assignment of $c$ is correct and unique.
\end{proof}

\begin{lemma}\label{lem:alg_cost}
  Algorithm~\ref{alg:tree} outputs a solution of cost at most $O(\log D)\cdot \cost_{\DLA}(z)$.
\end{lemma}
\begin{proof}
Recall that $\cost_{\DLA}(z)=\sum_{f\in\tilde{F}} \hat h(z^f)$.
We start by observing that the value of $\cost_{\DLA}(z)$ can not increase over time when $z$ changes during the execution of the algorithm. Indeed, Steps \eqref{alg:choose-theta} and \eqref{alg:buying-integrals} can only decrease the entries of $z$, hence $\cost_{\DLA}(z)$ by the monotonicity of $\hat{h}(\cdot)$. The only other changes of $z$ happen in Step \eqref{alg:merging}. Let us interpret this step as iteratively decreasing to zero $z^{f'}$ for each $f'\in \tilde{F}_v\setminus \{f_v\}$ and increasing $z^{f_v}$ by the same amount. The decrease of the cost at each step is $\hat{h}(z^{f_v})+\hat{h}(z^{f'})-\hat{h}(z^{f_v}+z^{f'})$. By the alternative definition of $\hat{h}(\cdot)$ as in \eqref{eq:lovasz-extension-bis} and its convexity, one has
$
  \hat{h}(z^{f_v}+z^{f'})=2\hat{h}\left(\frac{z^{f_v}+z^{f'}}{2}\right)\leq 2\left(\frac{1}{2}\hat{h}(z^{f_v})+\frac{1}{2}\hat{h}(z^{f'})\right)= \hat{h}(z^{f_v})+\hat{h}(z^{f'}).
$
Hence the decrease of the cost is non-negative as required.

For each facility $f$ and level $i$, let $\Delta^{\theta}_i (f)$ be the clients added to $S^f$ in Step \eqref{alg:choose-theta} during iteration $i$ (possibly $\Delta^{\theta}_i(f)=\emptyset$). We define similarly $\Delta^{1}_i (f)$ w.r.t.\ Step \eqref{alg:buying-integrals}. Notice that, by the submodularity (hence subadditivity) of $h(\cdot)$, the increase of the cost of the solution due to adding $\Delta$ to $S^f$ is at most $h(\Delta)$. Therefore we can upper bound the cost of the final solution $S=(S^f)_{f\in \tilde{F}}$ by
$$
  \cost_{\DLA}(S)\coloneqq \sum_{f\in \tilde{F}}h(S^f)\leq \sum_{i=0}^{D}\sum_{f\in \tilde{F}}\Big(h(\Delta^{\theta}_i (f))+h(\Delta^{1}_i (f))\Big).
$$
Let us upper bound the right-hand side of the above inequality. Let $z(i)$ denote the value of $z$ at the beginning of iteration $i$. From the previous observation, we have $\hat{h}(z(i))\leq \hat{h}(z)$ for every $i$. By Lemma \ref{lem:BO20} with $\alpha=\frac{1}{\log (D+1)}$, for any $\Delta^1_i(f)$ one has $h(\Delta^1_i(f))\leq \frac{1}{D+1}\hat{h}(z^f(i))$. Thus
\begin{equation}\label{eq:bound-delta-one}
  \sum_{i=0}^{D}\sum_{f\in \tilde{F}}h\big(\Delta^{1}_i (f)\big)\leq
  \sum_{i=0}^{D}\sum_{f\in \tilde{F}}\frac{1}{D+1}\hat{h}\big(z^f(i)\big)\leq
  \sum_{i=0}^{D}\frac{1}{D+1}\cost_{\DLA}(z(i))\leq
  \cost_{\DLA}(z).
\end{equation}

Let $z(D+1)$ be the value of $z$ at the end of the $D$-th iteration, hence in particular $\cost_{\DLA}(z(D+1))\geq 0$. Notice that $z=z(0)$. We can lower bound $\cost_{\DLA}(z)$ by
$$
  \cost_{\DLA}(z)\geq\sum_{i=0}^{D}\Big(\cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1))\Big).
$$
Let $z_1(i)$ be the value of $z$ obtained from $z(i)$ after applying Step \eqref{alg:merging} for all nodes of level $D-i$. Let also $z_2(i)$ be the value obtained from $z_1(i)$ if, for all the facilities $F'_i$ where Step \eqref{alg:choose-theta} is applied during iteration $i$, instead of setting $z^f_c=0$ one sets $z^f_c=\theta$ for the corresponding value of $\theta$. For the facilities not in $F'_i$ we simply let $z_2^f(i)=z_1^f(i)$. Observe that $z(i+1)\leq z_2(i)\leq z_1(i)\leq z(i)$. One has
\begin{align*}
  & \cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1))\\
  \geq & \cost_{\DLA}(z_1(i))-\cost_{\DLA}(z(i+1)) \geq
  \cost_{\DLA}(z_1(i))-\cost_{\DLA}(z_2(i))\\
  = & \sum_{f\in \tilde{F}}\hat{h}\Big(z_1^f(i)\Big)-\hat{h}\Big(z_2^f(i)\Big)=
  \sum_{f\in F'_i}\hat{h}\Big(z_1^f(i)\Big)-\hat{h}\Big(z_2^f(i)\Big)\geq
  \frac{\sum_{f\in F'_i}h\big(\Delta^{\theta}_i(f)\big)}{32\log(D+1)}=
  \frac{\sum_{f\in \tilde{F}}h\big(\Delta^{\theta}_i(f)\big)}{32\log(D+1)}.
\end{align*}
In the first two inequalities above we used the monotonicity of $\hat{h}(\cdot)$, while in the last inequality the definition of $\alpha$-supported. Altogether
\begin{equation}\label{eq:bound-delta-theta}
    \sum_{i=0}^{D}\sum_{f\in \tilde{F}}h\Big(\Delta^{\theta}_i (f)\Big)\leq 32\log(D+1)\cdot \sum_{i=0}^{D}\Big(\cost_{\DLA}(z(i))-\cost_{\DLA}(z(i+1)) \Big)\leq O(\log D)\cdot \cost_{\DLA}(z).
\end{equation}
By the monotonicity of $h(\cdot)$, Step~\eqref{alg:pruning} cannot increase the cost of the solution, hence the claim.
\end{proof}


\section*{Acknowledgements}

Fateme Abbasi and Jaros\l{}aw Byrka were supported by Polish National Science Centre (NCN) Grant 2020/39/B/ST6/01641.
Marek Adamczyk was supported by Polish National Science Centre (NCN) Grant 2019/35/D/ST6/03060.
Miguel Bosch Calvo, Fabrizio Grandoni, Krzysztof Sornat and Antoine Tinguely were supported by the SNSF Grant 200021\_200731/1.

\bibliographystyle{alpha}
