
\section{Proof of Theorem~\ref{thm:rho_partial_random}}\label{proof:rho_partial_random}
\begin{proofw}
The proof is very similar to the proof of Theorem~\ref{thm:rho_parital}. Let $n' = |\CS{C}^*|$, $k = \lceil \rho n' \rceil$ and $a = \lfloor (1-\rho) n' \rfloor$. As opposed to the proof of Theorem~\ref{thm:rho_parital}, in this setting, $R^*$ is a random subset. Hence, we condition on $R^* = \CS{Y}$ for some fixed subset $\CS{Y} \subseteq \CS{C}^*$ of cardinality $k$. The proof proceeds as the proof of Theorem~\ref{thm:rho_parital}, until we reach Inequality~\eqref{eq:line_robust}. Conditioned on the event $\{R^* = \CS{Y}\}$, we have $A^* = \CS{C}^* \setminus \CS{Y}$ and by substituting $|A^*| = a$ in Inequality~\eqref{eq:line_robust}, we get that
\begin{align*}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \CS{A^*}}p(u)}{R^* = \CS{Y}}} &\leq
    a \cdot \left(\frac{1}{k+1} + \frac{1}{k+1} \sum_{j=1}^{k} \left( \E{ p(u_j)} + q\cdot d^*_{u_j}\right) \right) + q \sum_{u \in \CS{C}^* \setminus \CS{Y}} d^*_u \\
    &= \frac{a}{k+1} \left(1+  \E{\sum_{u \in \CS{Y}} p(u) } + q\sum_{u \in \CS{Y}} d^*_u \right) + q \sum_{u \in \CS{C}^* \setminus \CS{Y}} d^*_u , 
\end{align*}

Now, similarly to Theorem~\ref{thm:qrofl-competitive} we have $ \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \CS{Y}} p(u)}{R^* = \CS{Y}} } \leq 1 + 2q \sum_{u \in \CS{Y}}d^*_u$, together with Lemma~\ref{lem:price_factor_roflq}, we get that $\E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(A^*)}{R^* = \CS{Y}}} \leq (1+1/q)\frac{a}{k+1}(2 + 3q \sum_{u \in \CS{Y}} d^*_u) + (1+q) \sum_{u \in \CS{C}^* \setminus \CS{Y}} d^*_u$. Finally, we add the cost paid for the service of the points in $R^*$, and use the bound $\E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(R^*)}{R^* = \CS{Y}}} \leq 1 + 1/q + 2 (1+q) \sum_{u\in \CS{Y}} d^*_u$. We have 
\begin{align*}
    & \E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}({\CS{C}^*})}{R^* = \CS{Y}}} \\
    & \quad = \E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(A^*)}{R^* = \CS{Y}}} + \E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(R^*)}{R^* = \CS{Y}}} \\ 
    & \quad \leq  \left(1+\frac{1}{q}\right)\frac{a}{k+1}\left(2 + 3q \sum_{u \in \CS{Y}} d^*_u  \right) + (1+q) \sum_{u \in {\CS{C}^*} \setminus \CS{Y}} d^*_u +  1 + \frac{1}{q} + 2 (1+q) \sum_{u\in \CS{Y}} d^*_u\\
    & \quad = 
    \left(1+\frac{1}{q}\right)\left(\frac{2a}{k+1} + 1\right) + (1+q)\left( \frac{3a}{k+1} + 2 \right) \sum_{u\in \CS{Y}} d^*_u + (1+q) \sum_{u \in {\CS{C}^*} \setminus \CS{Y}} d^*_u.
\end{align*}
By taking the expectation over $R^*$, we get that
\begin{align}
\begin{split}
    \E{\text{\normalfont ALG}({\CS{C}^*})}  &\leq 
    \left(1+\frac{1}{q}\right)\left(\frac{2a}{k+1} + 1\right) + (1+q)\left( \frac{3a}{k+1} + 2 \right) \E{\sum_{u\in R^*} d^*_u} \\
    & \quad  + (1+q) \E{ \sum_{u \in A^*} d^*_u}.
\end{split}\label{eq:apx_r*}
\end{align}
Now since $R^* \subseteq {\CS{C}^*}$ is a uniformly random subset of cardinality $k$, we have $\E{\sum_{u\in R^*} d^*_u} = \frac{k}{n'}\sum_{u\in {\CS{C}^*}} d^*_u $, and likewise,  $\E{\sum_{u\in A^*} d^*_u} = \frac{a}{n'}\sum_{u\in {\CS{C}^*}} d^*_u $. By substituting these two equations in Equation~\eqref{eq:apx_r*}, we obtain
\begin{align*}
    \E{\text{\normalfont ALG}({\CS{C}^*})} & \leq \left(1+\frac{1}{q}\right)\left(\frac{2a}{k+1} + 1\right) + (1+q)\left( \frac{3a}{k+1} \frac{k}{n'}+ \frac{2k}{n'}+ \frac{a}{n'}
    \right) \sum_{u\in {\CS{C}^*}} d^*_u  \\
    &\leq \left(1+\frac{1}{q}\right)\left(\frac{2a}{k+1} + 1\right) + (1+q)\left( \frac{4a + 2k}{n'} \right) \sum_{u\in {\CS{C}^*}} d^*_u \\
    & \leq  \left(1+\frac{1}{q}\right)\left(\frac{2}{\rho} -1\right) + (1+q) \left(  4 - 2\rho  \right) \sum_{u\in {\CS{C}^*}} d^*_u,
\end{align*}
where in the last inequality we used the fact that $2a/(k+1) \leq 2(1/\rho - 1)$ and $(4a + 2k)/n' = (4n' - 2k)/n' \leq 4-2\rho$.
\end{proofw}
\section{Discussion}\label{sec:discussion}

In this work, we resolve the open question regarding the true performance of Meyerson's algorithm ($\rofl[]$) in the random-order model. Furthermore, we introduce a general family of algorithms in the form of $\rofl[]$, and derive the best algorithm in this family, $\rofl[\nicefrac{1}{2}]$, which achieves the state-of-the-art performance. We prove that $\rofl[\nicefrac{1}{2}]$ is $3$-competitive and that the best possible competitive-ratio for this problem is $2$. 


Several interesting questions remain open for future research.
First, the true performance of Meyerson's algorithm for non-uniform facility costs in the random-order model remains open. It would be interesting to see if our techniques can be used to obtain tight analysis for this case too. Another interesting direction is to study the performance of the simple deterministic algorithm by Fotakis~\cite{fotakis2007primal} in the random-order model, which is still unknown. We note that a slight modification of the instance in the proof of our lower bound (Theorem~\ref{thm:lower_bound}) shows that the competitive-ratio of Fotakis' algorithm is no better than $3$.\footnote{One can check that by multiplying all the distances in the metric space by a factor of $\delta$, the competitive-ratio of Fotakis' algorithm on the resulting instance approaches $3$ as $\delta$ approaches $0$.} 

Finally, a gap between the lower and upper bounds that we obtain for the facility location problem with uniform facility costs remains open. To the best of our knowledge, there are no candidate online algorithms in the literature which could outperform $\rofl[\nicefrac{1}{2}]$ and beat the competitive-ratio of $3$. Hence, if the competitive-ratio of $3$ is not optimal, new algorithmic ideas are needed to beat this bound.

\section{Hardness Result}\label{sec:hardness}

In this section, we show that no online algorithm can have a competitive-ratio better than $2$, even in the weaker online $\text{i.i.d.}$ model with full prior knowledge of the distribution. 

In the $\text{i.i.d.}$ model, we are given the metric space $(\CS{M},d)$, and a distribution $D$ over $\CS{M}$ upfront. Then, at each online round $\ell \in [n]$, the demand point $v_\ell$ is drawn independently from $D$. In this model, an algorithm $\text{\normalfont ALG}$ is called $c$-competitive, if for any input instance ${\cal I} = (\CS{M},d,D,n)$, it holds that $\E{\text{\normalfont ALG}({\cal I})} \leq c \cdot \E{\text{\normalfont OPT}({\cal I})}$, where the expectation is taken over $v_1,\dots,v_n \sim D$, and the internal randomness of the algorithm.

\begin{theorem}\label{thm:lower_bound}
Let $\text{\normalfont ALG}$ be an algorithm for online facility location in the $\text{i.i.d.}$ model, then, the competitive-ratio of $\text{\normalfont ALG}$ is at least $2 - o(1)$.
\end{theorem}

\begin{proof}
Let $m = n^2$. We construct a metric space with $m + \binom{m}{n}$ points. The metric space consists of two types of points: The first type consists of $m$ points, $x_1,\dots,x_m$, with $d(x_i,x_j) = 1$ for all $i,j\in [m]$. The second type of points are called \textit{subset points}. For each subset $\CS{I} \subseteq [m]$ of cardinality $n$, there is a point $s_{\CS{I}}$ with $d(s_\CS{I},x_j) = 1/2$ if $j \in \CS{I}$ and $d(s_\CS{I},x_j) = 1$ otherwise. Finally, for two subset points $s_\CS{I} \neq s_\CS{J}$, $d(s_\CS{I},s_\CS{J}) = 1$. For the distribution $D$, we take the uniform distribution over $\{x_1,\dots,x_m\}$. 

To upper bound the cost of $\text{\normalfont OPT}$, observe that the set of arriving demand points $\{v_1,\dots,v_n\}$ is a subset of the points in $\{x_1,\dots,x_m\}$ of cardinality at most $n$, and therefore, there is a subset point $s_{\CS{I}}$ at distance at most $1/2$ from all the arriving demand points. Hence, $\E{\text{\normalfont OPT}} \leq 1 + n/2$.

We now consider the performance of $\text{\normalfont ALG}$. When a demand point $v_\ell$ arrives at $x_i$, we distinguish between three cases. First, if there is an open facility at $x_i$, the algorithm can serve the demand point at no cost. Second, if there is an open facility at a subset point $s_\CS{I}$ for $i \in \CS{I}$, the algorithm can assign the demand point to $s_{\CS{I}}$ at a cost of $1/2$. Otherwise, it must pay at least $1$ for serving $v_\ell$ (either by opening a facility at $v_\ell$ or by assigning it to an open facility).

To lower bound the cost of $\text{\normalfont ALG}$, we start by charging $\text{\normalfont ALG}$ a cost of $1$ for each demand point. Then, we substitute the cost saved by $\text{\normalfont ALG}$ due to demand points that arrive at the same location, and due to the opening of subset facilities. At online round $\ell \in [n]$, the probability that $v_\ell$ arrives at the same location as one of the previous demand points $\{v_1,\dots,v_{\ell-1}\}$, is at most $(\ell - 1)/m < n/m$. Hence, the expected cost saved by $\text{\normalfont ALG}$ for serving demand points that arrive at the same location is at most $n^2/m = 1$.

For the cost saved by subset facilities, when the algorithm opens a subset facility $s_{\CS{I}}$ at online round $\ell$, it pays an opening cost of $1$, and saves a cost of at most $1/2$ for the assignment cost of $v_\ell$ (the demand point at round $\ell$). Then, at each successive online round $j \in \{ \ell+1,\dots,n\}$, $s_{\CS{I}}$ saves a cost of at most $1/2$ if $v_j$ arrives at some $x_i$ for $i \in \CS{I}$, which happens with probability $n/m$. Hence, the expected cost saved by opening a facility at $s_\CS{I}$ is at most $1/2 + \frac{n^2}{2m} - 1 = \frac{n^2}{2m} - 1/2$ (note that we subtract $1$ to account for the facility opening cost). Since $m = n^2$, we have $\frac{n^2}{2m} - 1/2 = 0$, and so, the expected cost of $\text{\normalfont ALG}$ is not reduced by opening subset facilities.

We get that $\E{\text{\normalfont ALG}} \geq n - 1$. And so, $\E{\text{\normalfont ALG}}/\E{\text{\normalfont OPT}} \geq (n-1)/(1+n/2) = 2 - 6/(n+2)$, which approaches $2$ as $n$ approaches infinity.
\end{proof}



A simple and well-known result is that any $c$-competitive online algorithm in the random-order model, is also $c$-competitive in the $\text{i.i.d.}$ model (see e.g.,~\cite{gupta2022random,mehta2013online}). Hence, we have the following corollary.


\begin{corollary}
Let $\text{\normalfont ALG}$ be an algorithm for online facility location, then, the random-order competitive-ratio of $\text{\normalfont ALG}$ is at least $2 - o(1)$.
\end{corollary}
\section{Introduction}\label{sec:intro}


In the classical online metric uncapacitated facility location problem, we have a metric space where facilities can be opened at any point for a given cost (uniform facility cost). A sequence of demand points arrive one by one over time, and upon arrival of a demand point, it must be irrevocably assigned to an open facility. A demand point can either be assigned to an existing open facility, or a new facility can be opened for this purpose. The cost of assigning a demand point to a facility is the distance between the demand point and the facility. The goal is to minimize the total cost (assignment cost and facility opening cost) paid for serving all the demand points.


This problem was first considered by Meyerson~\cite{meyerson2001online}, and it has been studied extensively since (see e.g.,~\cite{anagnostopoulos2004simple, fotakis2003competitive, fotakis2007primal, jiang2021online, almanza2021online, fotakis2021learning, azar2022online} and the survey by Fotakis~\cite{fotakis2011online} and references therein). In his seminal paper~\cite{meyerson2001online}, Meyerson studied the problem both in the standard worst-case (adversarial order) model, and mainly in the random-order model, which is particularly suitable for many applications of the facility location problem.

Meyerson considered what is arguably the most simple and natural online algorithm for the facility location problem, which we call $\rofl[]$: When a demand point arrives, $\rofl[]$ randomly decides whether to assign it to an existing open facility, or to open a new facility at the demand point. The decision is based only on the distance, $r$, between the demand point and the nearest open facility (which is the assignment cost to this facility), and the facility opening cost $f$. $\rofl[]$ opens a new facility with probability $\min\{r/f,1\}$, and otherwise, it assigns the demand point to the nearest open facility. 

$\rofl[]$ has many advantages: it is simple and intuitive, very efficient computationally and memoryless. It has inspired many studies, and it is used as a building block in algorithms for other online problems (see e.g.,~\cite{guha2003clustering, charikar2003better,  fotakis2007primal, fotakis2011online, fotakis2021learning}). Meyerson's elegant analysis of $\rofl[]$ is one of the cornerstones of random-order analysis, and is sometimes taught in algorithms classes~\cite{lecture_roughgarden, gupta2022random}.

In the worst-case adversarial-order model, the facility location problem is considered to be solved. Shortly after the seminal paper by Meyerson, Fotakis showed that $\rofl[]$ is optimal $O(\log{n}/\log{\log{n}})$-competitive in the worst-case~\cite{fotakis2003competitive}. In contrast, this is not the case in the random-order model. In~\cite{meyerson2001online}, Meyerson showed that $\rofl[]$ is $8$-competitive, and it remained the best-known competitive-ratio for the problem until now.

The role of $\rofl[]$ for the online facility location problem is similar to the role of RANKING for the online bipartite matching problem. They are both simple and natural, and we want to understand if they achieve the best performance. Conducting tight analysis of the most natural and simple online algorithms has proven to be challenging in the random-order model. 
For instance, RANKING 
was tightly analyzed in the worst-case in the seminal paper by Karp et al.~\cite{karp1990optimal} (see also~\cite{goel2008online, birnbaum2008line,devanur2013randomized,eden2021economics}). However, while advances were made over the years, the exact competitive-ratio of RANKING is still an interesting open question in the random-order model~\cite{mehta2013online,karande2011online,mahdian2011online}. This is also the case for the classical FirstFit and BestFit algorithms for the online bin packing problem. Their performance in the worst-case was tightly analyzed in the 1970s~\cite{johnson1974worst} (see also~\cite{dosa2013first, dosa2014optimal}), while there are still gaps remaining in the random-order model~\cite{kenyon1996best, albers2021best}. In contrast, for $\rofl[]$, we overcome this challenge and give a tight analysis in the random order model. 

In some cases, tailoring an optimal algorithm in the random-order model compromises its performance in the worst-case, and vice versa~\cite{kaplan2020competitive}. Analyzing a single algorithm in both the worst-case and the random-order model provides a deeper understanding of its performance in different conditions, and sets new standards in the design of online algorithms~\cite{mirrokni2012simultaneous, raghvendra2016robust, molinaro2017online, gupta2021random}. The ideal is to have the ``best-of-both-worlds'' algorithm, i.e., a single algorithm with good performance guarantees in both models. $\rofl[]$ is a good example for this, it provides the best performance guarantee in the worst-case (asymptotically), and when the online sequence arrives in random order, it provides a much better guarantee. 


In this paper, we study the online facility location problem in the random order model. We provide tight bounds on the competitive-ratio of $\rofl[]$. We then design an improved algorithm that admits a better competitive-ratio while maintaining all the advantages of $\rofl[]$. We show that the performance of our improved algorithm is close to optimal by proving a lower bound on the performance of any algorithm for the problem. We also prove that the algorithms that we consider have a nice robustness property to partial adversarial orders. High-level details follow.


\subsection{Our Contribution}

We provide tight bounds on the performance of $\rofl[]$ in the random-order model, and show that its exact competitive-ratio is $4$. 

Our analysis maintains the elegancy in Meyerson's analysis, and even simplifies some aspects of it. In common with Meyerson's analysis, our analysis is done per cluster of the optimal solution. The crux of our analysis lies in pinpointing a subtle probabilistic event of opening a facility which is, roughly speaking, well placed among the remaining demand points in the cluster. This opened facility provides an upper bound on the expected distances between the following demand points and their closest open facility (which, in turn, upper bounds the expected cost incurred by serving these demand points). On the other hand, we also need to upper bound the cost incurred by serving the demand points that arrive before this event occurs. The choice of this event carefully balances these two things.






Our analysis sheds new light on the trade-off between assigning demand points to existing  facilities at a low cost, and opening new facilities for future use. It allows us to generalize $\rofl[]$ and consider a family of algorithms that open facilities with different probabilities. 

More concretely, we consider a generalized version of $\rofl[]$ that when a demand point arrives, instead of opening a facility with probability $\min\{r / f, 1\}$, it opens a facility with probability $g(r)$, for some function $g : \mathbb{R}_{\geq 0} \rightarrow [0,1]$. We show that the best functions has the form $g(r) = \min\{ q \cdot r / f , 1\}$ for some $q \in (0,1)$. Our analysis generalizes to provide tight bounds on the competitive-ratio of this generic algorithm for any value of $q$. The best competitive-ratio of an algorithm in this family is $3$ and it is obtained for $q=1/2$. We call this algorithm $\rofl[\nicefrac{1}{2}]$. We note that $\rofl[\nicefrac{1}{2}]$ is still (asymptotically) optimal in the worst-case adversarial-order model, and therefore it has the ``best-of-both-worlds'' property. 

We then prove a lower-bound of $2$ on the competitive-ratio of any algorithm for the facility location problem, which applies even in the weaker online $\text{i.i.d.}$ model. In the $\text{i.i.d.}$ model, the demand points are drawn independently from a probability distribution over the points in the metric space, and the online algorithm has full prior knowledge of this distribution. 

Finally, we study how well $\rofl[]$ performs in a partial adversarial order setting. We consider a setting in which 
for a parameter $\rho \in (0,1)$,
an adversarially chosen $(1-\rho)$-fraction of the demand points arrive in adversarial order. The remaining demand points in each cluster of the optimal solution are injected in random positions between the adversarially ordered points of the cluster. In this setting, we show that the competitive-ratio of $\rofl[]$, is within a factor of at most $(2-\rho)/\rho$ from its random-order competitive-ratio. For instance, our analysis shows that $\rofl[\nicefrac{1}{2}]$ is $3.66$-competitive if $10\%$ of the demand points arrive in adversarial order. This result can be seen as part of a growing body of work on robust random-order algorithms and non-uniform arrival orders that aim to weaken the random order assumption~\cite{kesselheim2015secretary, bradac2020robust, argue2022robust, kesselheim2020knapsack}.


\section{\texorpdfstring{$\rofl[]$}{DistProb} (Meyerson's Algorithm) is \texorpdfstring{$4$}{4}-Competitive}\label{sec:meyerson}

In this section, we analyze the fundamental randomized online algorithm, described in Algorithm~\ref{alg:rofl}, which was first introduced by Meyerson~\cite{meyerson2001online}. We refer to this algorithm by the name $\rofl[]$.

\IncMargin{1em}
\begin{algorithm}[ht]
\caption{$\rofl[]$}\label{alg:rofl}
$F_0 \leftarrow \emptyset$\;
\For {a demand $v_{\ell}$ that arrives at round $\ell$ } {
    $r(v_\ell) \leftarrow d(F_{\ell-1},v_\ell)$\;
    $p(v_\ell) \leftarrow \min\{r(v_\ell), 1\}$\;
    Flip a coin with probability $p(v_\ell)$ of Heads\; \label{line:heads}
    \uIf{Heads}{
        \tcp{Open a facility at $v_\ell$}
        $F_{\ell} \leftarrow F_{\ell-1} \cup \{v_\ell\}$\;
    } \Else {
        $F_{\ell} \leftarrow F_{\ell - 1}$
    }

    Assign $v_\ell$ to its nearest facility in $F_\ell$\;
}
\end{algorithm}
\DecMargin{1em}


For a demand point $u\in {\CS{U}}$ and online round $\ell \in [n]$, let $r(\ell, u) = d(F_{\ell-1}, u)$ be the distance between $u$ and the closest facility in $F_{\ell-1}$ and let $p(\ell,u) = \min\{r(\ell,u), 1\}$. Note that $p(\ell,u)$ is exactly the probability of Heads in line~\ref{line:heads} of Algorithm~\ref{alg:rofl} when $v_\ell = u$.

We bound the cost of $\rofl[]$ for each cluster of $\text{\normalfont OPT}$ separately. Consider a cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$ with center ${c^*}$. For $u \in {\CS{C}^*}$, we denote $d^*_u = d({c^*},u)$. The cost of $\text{\normalfont OPT}$ for serving ${\CS{C}^*}$ is $ \text{\normalfont OPT}({\CS{C}^*}) = 1 + \sum_{u\in {\CS{C}^*}} d^*_u$.

We partition the demand points in ${\CS{C}^*}$ into simpler subsets, and bound the expected cost of $\rofl[]$ on each subset separately. The next lemma shows that to bound the cost that $\rofl[]$ pays for the service of the demands in some subset $\CS{X} \subseteq {\CS{C}^*}$, it suffices to bound $\E{\sum_{u \in \CS{X}} p(u)}$.
\begin{lemma}\label{lem:price_factor}
The expected service cost of $\rofl[]$ for a demand $u$ is at most $2 \cdot \E{ p(u)}$
\end{lemma}

\begin{proof}
Fix $u \in {\CS{U}}$. Let $\text{\normalfont ALG}(u)$ be the cost that $\rofl[]$ pays for serving $u$. Let $p \in [0,1]$. Conditioned on $p(u) = p$, if $p = 1$, the algorithm open a facility at $u$ and pays $1 < 2 = 2p$ ($1$ for the facility opening cost, and $0$ for the assignment cost). Otherwise, $p(u) = r(u)$, and the algorithm opens a facility at $u$ with probability $p$ and pays $1$, and with probability $1-p$, it serves $u$ through an open facility at distance $p$ and pays $p$. Hence, $\E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(u)}{p(u) = p}} = p \cdot 1 + (1- p)\cdot p = 2 p - p^2 \leq 2p$. The lemma follows by taking the expectation over $p(u)$.
\end{proof} 

The basic idea of the analysis is to wait until the first facility at a point from ${\CS{C}^*}$ is opened, and to use this facility to upper bound the distances of all successive demand points in ${\CS{C}^*}$ from their closest open facility. However, it turns out that using the first opened facility does not provide an adequate upper bound on the distances. Instead, we use the first facility which is opened at, roughly speaking, a ``uniform" location among the remaining demand points in ${\CS{C}^*}$. 

For the analysis we distinguish between a \textit{balanced} and \textit{imbalanced} opening of a facility. For an online round $\ell \in [n]$, let $\cpoints{\ell}={\CS{C}^*} \cap \{v_{\ell},\dots,v_{n}\}$ be the set of remaining demand points in ${\CS{C}^*}$ at round $\ell$. Also, for $x \in \mathbb{R}_{\geq 0}$, let $\closer{\ell}{x} = \{u \in \cpoints{\ell} : d^*_{u} \leq x\}$, that is, $\closer{\ell}{x}$ is the set of demand points in $\cpoints{\ell}$ whose distance from $c^*$ is at most $x$.
When a demand point $v_\ell \in \cpoints{\ell}$ arrives (at online round $\ell$), we consider the demand point 
\begin{align*}
    w(v_\ell) = \argmin_{u \in \closer{\ell}{ d^*_{v_{\ell}} } } {p(\ell,u)},
\end{align*} 
i.e., $w(v_\ell)$ is a point in $\closer{\ell}{ d^*_{v_{\ell}} }$ with a minimal distance to an open facility (in $F_{\ell-1}$).\footnote{Ties are broken arbitrarily.} We illustrate the definition of $w(v_\ell)$ in Figure~\ref{fig:w_def}. The red points are the open facilities in $F_{\ell-1}$ and the blue points are the demand points in $\closer{\ell}{d^*_{v_\ell}}$. The red lines connect each demand point to its closest open facility (regardless of the line pattern). The dotted red line is the shortest distance between a demand point in $\closer{\ell}{d^*_{v_{\ell}}}$, and an open facility in $F_{\ell-1}$.
\input{drawing}


Recall that the algorithm flips a coin and opens a facility at $v_\ell$ with probability $p(v_\ell)$. We call this coin the \textit{algorithm's coin}.
To make our distinction, we flip an additional independent coin, which we call the \textit{analysis' coin}, with probability $p(\ell,w(v_\ell))/p(v_\ell)$ of Heads (note that $p(\ell,w(v_\ell))/p(v_\ell) \leq 1$). We say that a \textit{balanced} facility is opened at $v_\ell$ if the algorithm's coin comes up Heads (a facility is opened at $v_\ell$ by the algorithm) and the analysis' coin comes up Heads. If the algorithm's coin comes up Heads and the analysis' coin comes up Tails, we say that an \textit{imbalanced} facility is opened at $v_\ell$. Observe that overall, a balanced facility is opened at $v_\ell$ if both coins come up Heads which happens with probability $p(v_\ell) \cdot p(\ell,w(v_\ell))/p(v_\ell) =  p(\ell,w(v_\ell))$, and an imbalanced facility is opened at $v_\ell$ with probability $p(v_\ell) -  p(\ell,w(v_\ell))$. 

The expected distance of the first balanced facility from $c^*$ is relatively small. Therefore, it provides us with a good upper bound on the expected distance of all successive demand points from their nearest open facility. This will become clearer in the following two lemmas. 

We are now ready to define a partition of ${\CS{C}^*}$ into simpler subsets. Let $T$ be the online round in which the first balanced facility from ${\CS{C}^*}$ is opened (that is, a balanced facility $v_T \in \cpoints{T}$ is opened). If there is no such demand point, we define $T= n+1$. Until online round $T$, the algorithm processes points from ${\CS{C}^*}$ which are in the set $\uptocpoints{T} = \{v_1,\dots,v_T\} \cap {\CS{C}^*}$.
We now derive upper bounds on the expected service cost of the algorithm for each of the subset, $\uptocpoints{T}$ and $\cpoints{T+1}$, separately. 

We first prove an upper bound for the demand points in $\cpoints{T+1}$.

\begin{lemma}\label{lem:C_Tplus1}
$\E{\sum_{u \in \cpoints{T+1}} r(u)} \leq \E{ \sum_{u \in \cpoints{T}} d^*_u} + \E{(|\cpoints{T}| - 2)d^*_{v_T}}$.
\end{lemma}

\begin{proof}
Observe that each demand point $u \in \cpoints{T+1}$ can be served by the open facility at $v_T$, and thus $\E{r(u)} \leq \E{d^*_{v_T} + d^*_u}$. Hence, we get that
\begin{align*}
    \E{\sum_{u \in \cpoints{T+1}} r(u)} &\leq \E{\sum_{u \in \cpoints{T+1}} \left(d^*_{v_T} + d^*_u\right)} 
    = \E{ \left| \cpoints{T+1} \right| d^*_{v_T} + \sum_{u \in \cpoints{T+1}} d^*_u} \\
    &= \E{(|\cpoints{T+1}| - 1)d^*_{v_T} +\sum_{u \in \cpoints{T}} d^*_u } = \E{(|\cpoints{T}| - 2)d^*_{v_T}}  +\E{\sum_{u \in \cpoints{T}} d^*_u },
\end{align*}
where the second equality follows from the fact that $\cpoints{T} = \cpoints{T+1} \cup \{v_T\}$, and also the last inequality is due to the fact that $|\cpoints{T+1}| = |\cpoints{T}| - 1$.
\end{proof}

Since for all $u \in \CS{U}$, $p(u) = \min\{r(u),1\} < r(u)$, we have the following immediate corollary.
\begin{corollary}\label{cor:C_Tplus1}
$\E{\sum_{u \in \cpoints{T+1}} p(u)} \leq \E{ \sum_{u \in \cpoints{T}} d^*_u} + \E{(|\cpoints{T}| - 2)d^*_{v_T}}$.
\end{corollary}

In the following lemma, we use the fact that a balanced facility is opened at $v_{T}$ to upper bound its distance, $d^*_{v_T}$, from $c^*$, in terms of the distances of the demand points in $\cpoints{T}$ from $c^*$. 
For each demand point $u \in \cpoints{T}$, the probability that it opens as a balanced facility is a fraction of 
the probability that it opens at all. We defined these fractions such that the probability that $u$ is opened as balanced is monotone non-increasing in $d^*_u$. This way, it is at least as likely that a new balanced facility is opened at a demand point near ${c^*}$ 
than at a demand point further away from ${c^*}$. Hence, the expected distance of $v_T$ from $c^*$ is no larger than the average distance of the demand points in $\cpoints{T}$ from $c^*$. This is a crucial part of our analysis and we formalize this in the next lemma.

\begin{lemma}\label{lem:exp_v_T}
$\E{|\cpoints{T}|\cdot d^*_{v_T}} \leq \E{\sum_{u \in \cpoints{T}} d^*_{u}}$.
\end{lemma}
\begin{proof}

Let $\ell \in [n + 1]$. We condition on the event $\{T = \ell\}$, i.e., that the first balanced facility from ${\CS{C}^*}$ is opened at online round $\ell$ (recall that $T=n+1$ means that no balanced facility is opened). Observe that for $T=n+1$, we have $\cpoints{T} = \emptyset$, and the lemma holds.\footnote{For $T=n+1$, we define $d^*_{v_T} = 0$.} 

For $\ell \leq n$, we also condition on the online sequence until round $\ell$, $\bm{v}_{\ell-1} = (v_1,\dots,v_{\ell-1})$, and on the set of open facilities at the beginning of online round $\ell$, $F_{\ell-1}$. Let $\mathbf{x}_{\ell-1} = (x_1,\dots,x_{\ell-1})$ be a sub-sequence of the demand points and let $\CS{F} \subseteq {\CS{U}}$, such that $\Pr[ T=\ell, \bm{v}_{\ell-1} =\mathbf{x}_{\ell-1}, F_{\ell-1} = \CS{F}]\neq 0$.  For brevity, we denote the event $\{ T=\ell, \bm{v}_{\ell-1} =\mathbf{x}_{\ell-1}, F_{\ell-1} = \CS{F}\}$ by $ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F})$. 


Note that conditioned on $ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F}) $, $r(\ell,u)$ and $p(\ell,u)$ are fixed for all $u \in {\CS{U}}$. $r(\ell,u)$ gets the value $r_{\CS{F}}(\ell,u) = d(\CS{F}, u)$, and $p(\ell,u)$ gets the value $p_{\CS{F}}(\ell,u) = \min\{r_{\CS{F}}(\ell,u), 1\}$. 
Likewise, the set $\cpoints{\ell}$ is also fixed, and gets the value $\CS{Y} = \left( \CS{U} \setminus \{x_1,\dots,x_{\ell-1}\} \right) \cap {\CS{C}^*}$. Let $u_1,\dots,u_k$ be the demand points in $\CS{Y}$ ordered by their distance from ${c^*}$, i.e., $d^*_{u_1} \leq d^*_{u_2} \leq \dots \leq d^*_{u_k}$. Note that $k = | \CS{Y} | $. For $1\leq  j\leq k$, let $w_j = \argmin_{1 \leq  i \leq j} \{ p_{\CS{F}}(\ell, u_i)\}$. Note that $w_j$ is the value of $w(v_\ell)$ when $v_\ell = u_j$. We have 
\begin{align}
    \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{v_T = u_j}{ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F}) }\right] 
    &= \frac{ \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{v_T = u_j, T = \ell}{\bm{v}_{\ell-1} =\mathbf{x}_{\ell-1}, 
    F_{\ell-1} = \CS{F}}\right] } { \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{T = \ell} {\bm{v}_{\ell-1} =\mathbf{x}_{\ell-1}, 
    F_{\ell-1}} = \CS{F}\right] }.\label{eq:conditional_explanation}
\end{align}
Since each remaining demand point in ${\CS{U}}$ is equally likely to arrive at round $\ell$, $u_j$ arrives at round $\ell$ with probability $\frac{1}{n-\ell+1}$, and when $v_\ell = u_j$, a balanced facility is opened at $u_j$ with probability $p_{\CS{F}}(\ell, w_j)$ (by the definition of balanced opening of a facility). Hence, $\Pr[v_T = u_j, T = \ell \mid \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, F_{\ell-1} = \CS{F}] = \frac{1}{n-\ell+1} \cdot p_{\CS{F}}(\ell, w_j)$
and $\Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{T = \ell} {\bm{v}_{\ell-1} =\mathbf{x}_{\ell-1}, F_{\ell-1}}\right] = \sum_{i=1}^{k} \frac{1}{n-\ell+1} \cdot p_{\CS{F}}(\ell, w_i)$, therefore, by substituting the last two equations in Equation~\eqref{eq:conditional_explanation}, we obtain
\begin{align*}
    \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{v_T = u_j}{ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F}) }\right] = \frac{p_{\CS{F}}(\ell, w_j)}{\sum_{i=1}^{k} p_{\CS{F}}(\ell, w_i)}.
\end{align*}
Now since $d^{*}_{u_1} \leq \cdots \leq d^*_{u_k}$, and $p_{\CS{F}}(\ell, w_1) \geq p_{\CS{F}}(\ell, w_2) \geq \cdots \geq p_{\CS{F}}(\ell, w_k)$, we get that
\begin{align*}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{|\cpoints{T}| \cdot d^*_{v_T}}{ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F})}} &= k \cdot \E{\@ifstar\@giventhatstar\@giventhatnostar{ d^*_{v_T}}{ {\mathcal{E}} (\mathbf{x}_{\ell-1}, \CS{F})}} \\ &= k \cdot \sum_{j=1}^{k}  d^*_{u_j} \frac{p_{\CS{F}}(\ell, w_j)}{\sum_{i=1}^{k} p_{\CS{F}}(\ell, w_i) } \leq k \cdot \frac{1}{k} \sum_{j=1}^{k}  d^*_{u_j} = \sum_{u \in \CS{Y}}  d^*_{u}.
\end{align*}
To conclude the proof we take the expectation over $T$, $\bm{v}_{T-1}$ and $F_{T-1}$, and get that $\E{|\cpoints{T}| \cdot d^*_{v_T}} = \E{\sum_{u \in \CS{C}_T}  d^*_{u} }$.
\end{proof}

We now prove an upper bound for the demand points in $\uptocpoints{T}$. 
\begin{lemma}\label{lem:until_opening}
$\E{\sum_{u \in \uptocpoints{T}} p(u)} \leq 1 + 2 \cdot  \E{\sum_{u \in \uptocpoints{T}} d^*_{u}}$
\end{lemma} 

\begin{proof}
For $1\leq \ell \leq n$, let $T_\ell \geq \ell$ be the first online round (from round $\ell$ onward) in which a balanced facility is opened by the algorithm,
let $\tcpoints{\ell} = \{v_\ell,\dots,v_{T_\ell}\} \cap {\CS{C}^*}$, and let $P_\ell = \sum_{u \in \tcpoints{\ell}}p(u)$. Observe that $T_1 = T$ and so $\tcpoints{1} = \uptocpoints{T}$. Therefore, to prove the  statement of the lemma we need to show that $\E{ P_1 } \leq 1 + 2 \cdot  \E{\sum_{u \in \tcpoints{1}} d^*_{u}}$.

We condition on the online sequence until round $\ell$, $\bm{v}_{\ell-1} = (v_1,\dots,v_{\ell-1})$, and on the set of open facilities at the beginning of online round $\ell$, $F_{\ell-1}$.
We prove by downwards induction on $\ell$ that for any $\CS{F} \subseteq {\CS{U}}$ and any sub-sequence of the demand points $\mathbf{x}_{\ell-1} = (x_1,\dots,x_{\ell-1})$ such that $\Pr[\bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}] \neq 0$, it holds that $\E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{\bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}}} \leq 1 + 2  \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}}{ \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}} }$.


For $\ell = n$, we have $P_n = p(v_n)$ if $v_n \in {\CS{C}^*}$ and $0$ otherwise. Since $p(v_n) \leq 1$, we have for any $\mathbf{x}_{n-1}$ and $\CS{F}$ (such that $\Pr[\bm{v}_{n-1} = \mathbf{x}_{n-1}, F_{n-1} = \CS{F}] \neq 0$), that $\E{\@ifstar\@giventhatstar\@giventhatnostar{P_n}{\bm{v}_{n-1} = \mathbf{x}_{n-1}, F_{n-1} = \CS{F}}} \leq 1$.

Now let $\ell < n$. Let $\CS{F} \subseteq {\CS{U}}$, and let $\mathbf{x}_{\ell-1} = (x_1,\dots,x_{\ell-1})$ be a sub-sequence of the demand points of length $\ell-1$. As in the proof of Lemma~\ref{lem:exp_v_T}, conditioned on $\{F_{\ell-1} = \CS{F}, \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}\}$, $r(\ell,u)$ and $p(\ell,u)$ are fixed for all $u \in {\CS{U}}$, and get the values $r_{\CS{F}}(\ell,u) = d(\CS{F}, u)$, and $p_{\CS{F}}(\ell,u) = \min\{r_{\CS{F}}(\ell,u), 1\}$, respectively. 
Also $\cpoints{\ell}$ gets the value $\CS{Y} = \left( \CS{U} \setminus \{x_1,\dots,x_{\ell-1}\} \right) \cap {\CS{C}^*}$. Let $u_1,\dots,u_k$ be the demand points in $\CS{Y}$ ordered by their distance from ${c^*}$, i.e., $d^*_{u_1} \leq d^*_{u_2} \leq \dots \leq d^*_{u_k}$, and for $1\leq  j\leq k$, let $w_j = \argmin_{1 \leq  i \leq j} \{ p_{\CS{F}}(\ell, u_i)\}$. Note that $w_j$ is the value of $w(v_\ell)$ when $v_\ell = u_j$.


In what follows, we further condition on $v_\ell$, and show that the induction step holds for all possible values of $v_\ell$. We distinguish between two cases, $v_\ell \in \CS{Y}$ and $v_\ell \notin \CS{Y}$. We begin with the case $v_\ell \in \CS{Y}$.


For $u_j \in \CS{Y}$, let $\balanced{u_j}$ be the event that a balanced facility is opened at $u_j$. Likewise, let $\imbalanced{u_j}$ be the event that an imbalanced facility is opened at $u_j$, and let $\nofacility{u_j}$ be the event that no facility is opened at $u_j$. We have
\begin{align}
\begin{split}
    & \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{	
        \begin{array}{c}
            v_{\ell} = u_j,\\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
            F_{\ell-1} = \CS{F}
        \end{array}
        }
    }\\ 
    & \quad = \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{\balanced{u_j}}
        { 
            \begin{array}{c}
                v_{\ell} = u_j,\\
                \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
                F_{\ell-1} = \CS{F}
            \end{array} 
        } \right] \cdot p_{\CS{F}}(\ell, u_j) \\
        & \quad \quad  + \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{\imbalanced{u_j}}
        {
            \begin{array}{c}
                v_{\ell} = u_j,\\
                \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
                F_{\ell-1} = \CS{F}
            \end{array}
        } \right] \left( p_{\CS{F}}(\ell, u_j) + \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}}{ 	
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array} } } \right) \\
        & \quad \quad + \Pr\left[\@ifstar\@giventhatstar\@giventhatnostar{\nofacility{u_j}}
        {
            \begin{array}{c}
                v_{\ell} = u_j,\\
                \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
                F_{\ell-1} = \CS{F}
            \end{array}
        } \right] \left( p_{\CS{F}}(\ell, u_j) +  \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}}{	
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array} }
        } \right).
\end{split}\label{eq:p_l_explained}
\end{align}

By the definition of balanced opening of a facility, the (conditional) probabilities of the events $\balanced{u_j}$, $\imbalanced{u_j}$ and $\nofacility{u_j}$ are $p_{\CS{F}}(\ell, w_j)$, $\left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)$ and $\left(1-  p_{\CS{F}}(\ell, u_j)\right)$, respectively. By substituting these probabilities in Equation~\eqref{eq:p_l_explained} and using the induction hypothesis (twice) and get that
\begin{align}
\begin{split}
    & \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{ 
        \begin{array}{c}
            v_{\ell} = u_j,\\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
            F_{\ell-1} = \CS{F}
        \end{array}
        }
    } \\
    & \quad \leq p_{\CS{F}}(\ell, u_j) + \left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right) \left(1 + 2 \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u} }{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array} } }\right) \\
    &  \quad \quad +\left(1-  p_{\CS{F}}(\ell, u_j)\right) \left( 1+ 2\E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{ u \in \tcpoints{\ell+1}} d^*_{u}}{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array} }
        } \right) \\
    &\quad  = 1 + \left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)  \\
    & \quad \quad + 2\left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)  \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u} }{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array} } } \\
    & \quad \quad  + 2\left(1-  p_{\CS{F}}(\ell, u_j)\right) \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}}{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array} }
        }.
\end{split}\label{eq:exp_round_l_2}
\end{align}

We now upper bound the term $\left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)$. Let $z = d(\CS{F}, {c^*})$ be the distance between ${c^*}$ ($\text{\normalfont OPT}$'s center of ${\CS{C}^*}$) and the closest open facility in $\CS{F}$. By the triangle inequality, we have $r_{\CS{F}}(\ell, u_j) \leq d^*_{u_j} + z$ and $z \leq  r_{\CS{F}}(\ell, w_j) + d^*_{w_j} \leq r_{\CS{F}}(\ell, w_j) + d^*_{u_j}$. Hence, 
$r_{\CS{F}}(\ell, u_j) \leq 2d^*_{u_j} + r_{\CS{F}}(\ell, w_j)$, and so 
\begin{align}
    r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j) \le  2d^*_{u_j} .\label{eq:triangle_dist}
\end{align}
Now since $r_{\CS{F}}(\ell, u_j) \geq r_{\CS{F}}(\ell, w_j)$, $p_{\CS{F}}(\ell, u_j) = \min\{r_{\CS{F}}(\ell, u_j),1\}$ and $p_{\CS{F}}(\ell, w_j) = \min\{r_{\CS{F}}(\ell, w_j),1\}$, it holds that $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \leq r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j)$. To see this, observe that if both $r_{\CS{F}}(\ell, u_j) \leq 1$ and $r_{\CS{F}}(\ell, w_j) \leq 1$, then  $p_{\CS{F}}(\ell, u_j) = r_{\CS{F}}(\ell, u_j)$ and $p_{\CS{F}}(\ell, w_j) = r_{\CS{F}}(\ell, w_j)$. If both $r_{\CS{F}}(\ell, u_j) > 1$ and $r_{\CS{F}}(\ell, w_j) > 1$ then $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) = 0 \leq r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j)$, and if $r_{\CS{F}}(\ell, u_j) > 1$ and $r_{\CS{F}}(\ell, w_j) \leq 1$, then  $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) = 1 - r_{\CS{F}}(\ell, w_j) <  r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j)$. Hence, we have
\begin{align}
p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \leq r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j) \leq 2d^*_{u_j}. \label{eq:triangle}
\end{align}

Now, observe that 
\begin{align}
\begin{split}
    & \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    } } \\ 
    & \quad =  p_{\CS{F}}(\ell, w_j) \cdot d^*_{u_j} + \left( p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \right) 
    \left( 
        d^*_{u_j} +
        \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
                \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array}
        } } 
    \right) \\
    & \quad \quad + \left(1 - p_{\CS{F}}(\ell, u_j)  \right) 
    \left( d^*_{u_j} + \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} { 
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }} \right) \\
    &\quad = d^*_{u_j} + \left( p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \right) 
    \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
                \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array}
        } }   \\
    & \quad \quad + \left(1 - p_{\CS{F}}(\ell, u_j)  \right) 
      \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} { 
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }}.
\end{split}\label{eq:exp_sum_dist}
\end{align}
Thus, by substituting~\eqref{eq:triangle} in~\eqref{eq:exp_round_l_2} and using Equation~\eqref{eq:exp_sum_dist}, we obtain
\begin{align}
\begin{split}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell} { 
        \begin{array}{c}
            v_\ell = u_j, \\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
            F_{\ell} = \CS{F}
        \end{array}
        } 
    } 
    &\leq  1 + 2  \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {        \begin{array}{c}
            v_\ell = u_j, \\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
            F_{\ell} = \CS{F}
        \end{array}
        }}.
\end{split}
\end{align}

For $v_\ell = u \in \CS{U} \setminus (\CS{Y} \cup \{x_1,\dots,x_{\ell-1}\} )$, we can consider only whether a facility is opened at $u$ or not. We have
\begin{align}
\begin{split}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{\begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}}} 
    &= p_{\CS{F}}(\ell, u) 
        \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}} { 
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u \}
            \end{array}}} \\
            & \quad + (1-p_{\CS{F}}(\ell, u)) 
        \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}}{
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
        }} \\
    &\leq 1 + 2 \cdot p_{\CS{F}}(\ell, u) 
        \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u \}
            \end{array}
        }} \\
    & \quad + 2 \cdot (1-p_{\CS{F}}(\ell, u)) \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }} \\
    &\leq 1 + 2 \cdot \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    } },
\end{split}\label{eq:not_in_C}
\end{align}
where in the first inequality we used the induction hypothesis, and the last inequality follows by the fact that, similarly to Equation~\eqref{eq:exp_sum_dist}, we have
\begin{align}
\begin{split}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }} 
    &=  p_{\CS{F}}(\ell, u) \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} { 
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u\}
            \end{array}
    }} \\
    & \quad + \left(1 - p_{\CS{F}}(\ell, u)  \right)  \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }}.
\end{split}\label{eq:notinc_expression}
\end{align}
To conclude the inductive argument we take the expectation over $v_\ell$.
\end{proof}

We are now ready to prove the competitive-ratio of the algorithm.

\begin{theorem}\label{thm:cr_meyerson}
$\rofl[]$ is $4$-competitive.
\end{theorem}

\begin{proof} 
For a cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$, we have ${\CS{C}^*} =  \uptocpoints{T} \cup \cpoints{T+1} $. By Lemma~\ref{lem:until_opening} and Corollary~\ref{cor:C_Tplus1} together with Lemma~\ref{lem:price_factor}, we get that
\begin{align*}
\E{\text{\normalfont ALG}\left({\CS{C}^*}\right)} &= \E{\text{\normalfont ALG}\left(\uptocpoints{T}\right)} +  \E{\text{\normalfont ALG}\left(\cpoints{T+1}\right)} \\
&\leq 2 \cdot \E{\sum_{u \in \uptocpoints{T}} p(u)} + 2 \cdot \E{\sum_{u \in \cpoints{T+1}} p(u)} \\
&\leq  2 + 4 \cdot  \E{\sum_{u \in \uptocpoints{T}} d^*_{u}} + 2 \cdot \E{ \sum_{u \in \cpoints{T}} d^*_u} + 2 \cdot \E{(|\cpoints{T}| - 2)d^*_{v_T}} \\
&= 2 + 4 \cdot  \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}}  + 4 \cdot \E{d^*_{v_T}} + 2 \cdot \E{ \sum_{u \in \cpoints{T}} d^*_u} + 2 \cdot \E{(|\cpoints{T}| - 2)d^*_{v_T}} \\
&= 2 + 4 \cdot  \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}} + 2 \cdot \E{ \sum_{u \in \cpoints{T}} d^*_u}  + 2 \cdot \E{(|\cpoints{T}|)d^*_{v_T}} \\
&\leq  2 + 4 \cdot  \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}} + 2 \cdot \E{ \sum_{u \in \cpoints{T}} d^*_u}  + 2 \cdot \E{\sum_{u \in \cpoints{T}} d^*_{u}} = 2 + 4 \cdot  \E{\sum_{u \in {\CS{C}^*}} d^*_{u}}.
\end{align*}
Where in the last inequality we used Lemma~\ref{lem:exp_v_T}. Now since $\text{\normalfont OPT}({\CS{C}^*}) = 1 + \sum_{u \in {\CS{C}^*}} d^*_u$, we have $\E{\text{\normalfont ALG}({\CS{C}^*})} / \text{\normalfont OPT}({\CS{C}^*}) \leq 4$. Since this is true for each cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$, we get that $\E{\text{\normalfont ALG}}/\text{\normalfont OPT} \leq 4$.
\end{proof}


We now show that our analysis of $\rofl[]$ is tight.

\begin{theorem}\label{thm:tight_4}
There is an infinite sequence of input instances ${\cal I}_{1},{\cal I}_{2},\dots$, with increasing number of demand points and decreasing distances between the demand points, where the competitive-ratio of $\rofl[]$ on ${\cal I}_{k}$ approaches $4$ as $k \rightarrow \infty$.
\end{theorem}

\begin{proof}
In the instance ${\cal I}_{k}$ the metric space consists of $k+1$ points $\{u_1,\dots,u_k, {c^*}\}$ where $d(u_i,u_j) = 2 \delta$ for all $i\neq j$ and $d(u_i, {c^*}) = \delta$ for all $1 \leq i \leq k$ and $\delta =  1/(4 \sqrt{k})$ (observe that $2 \delta < 1$ for all $k \in \mathbb{N}$). The demand points are  ${\CS{U}} = \{u_1,\dots,u_k\}$. $\rofl[]$ opens a facility at $v_1$ and pays $1$. Then, for each demand $v_\ell$ that arrives at round $\ell \in \{2,\dots,k\}$ we have $d(F_{\ell-1},v_\ell) = 2\delta$, regardless of the decisions of the algorithm in previous rounds. Hence, the expected cost of the algorithm for serving $v_\ell$ is $2\delta \cdot 1 + (1-2\delta)\cdot 2\delta = 4\delta - 4\delta^2$. Hence, 
\begin{align*}
    \E{\text{\normalfont ALG}({\cal I}_{k})} = 1 + (k-1)(4\delta - 4\delta^2).
\end{align*}

On the other hand, $\text{\normalfont OPT}$ can open a facility at ${c^*}$ and serve each demand by ${c^*}$ at a cost of $\delta$. Thus, $\E{\text{\normalfont OPT}} \leq 1 + k\delta$. To conclude

\begin{align*}
    \frac{\E{\text{\normalfont ALG}({\cal I}_{k})}}{\text{\normalfont OPT}({\cal I}_{k})} \geq \frac{1 + (k-1)(4\delta - 4\delta^2)}{1+k\delta} = \frac{1 + (k-1)(1/\sqrt{k} - 1/k)}{1+\sqrt{k}/4},
\end{align*}
which approaches $4$ as $k \rightarrow \infty$.
\end{proof}

\section{Improving \texorpdfstring{$\rofl[]$}{DistProb}}\label{sec:improve}
In this section, we present a modified version of $\rofl[]$ with an improved competitive-ratio. Our construction in Theorem~\ref{thm:tight_4} will be useful to guide us towards the improved algorithm. Observe that on our constructed instances in Theorem~\ref{thm:tight_4}, after the first facility is opened at $v_1$, opening additional facilities at future demand points $v_2,\dots,v_n$ does not reduce the service cost. Nevertheless, $\rofl[]$ randomly opens a facility at each arriving demand point $v_\ell$ with probability $p(v_\ell) = 2 \delta$, which leads to an expected service cost of $4\delta- 4\delta^2$, while $\text{\normalfont OPT}$ pays only $\delta$. In this way, we get the competitive-ratio of $4$. On these instances, reducing the probability of opening a facility results in better performance.

Generally, we modify the probability of opening a facility at a demand point $v_\ell$ at distance $r = d(F_{\ell-1}, v_\ell)$ and reduce it from $\min\{r,1\}$ to some probability $g(r)$, for $g : \mathbb{R}_{\geq 0} \rightarrow [0,1]$ (see Algorithm~\ref{alg:rofl_q} for a formal description). Observe that for $r \geq 1$, it is always better to open a facility (with probability $1$), and for $r = 0$ there is no reason to open an additional facility. Therefore, we can focus our attention on $r \in (0,1)$.

\IncMargin{1em}
\begin{algorithm}[ht]
\caption{Generic $\rofl[]$}\label{alg:rofl_q}
$F_0 \leftarrow \emptyset$\;
\For {a demand $v_{\ell}$ that arrives at round $\ell$ } {
    $r(v_\ell) \leftarrow d(F_{\ell-1}, v_\ell)$\;
    $p(v_\ell) \leftarrow g(r(v_\ell))$\;\label{line:flip_start}
    Flip a coin with probability $p(v_\ell)$ of Heads\; \label{line:roflq_heads}
    \uIf{Heads}{
        $F_{\ell} \leftarrow F_{\ell-1} \cup \{v_\ell\}$\;
    } \Else {
        $F_{\ell} \leftarrow F_{\ell - 1}$
    }\label{line:flip_end}

    Assign $v_\ell$ to the nearest facility in $F_\ell$\;
}
\end{algorithm}
\DecMargin{1em}

By our observation above, to improve upon the competitive-ratio of $4$ we need $g(r) < r$. Next, we construct another example to derive a lower bound on $g(r)$. Concretely, we show that to get an improvement, $g$ must satisfy $g(r) > r/4$. These two bounds leads us to the choice of a function $g$ of the form $g(r) = q \cdot r$ for some $q \in (1/4,1)$.

We now derive the lower bound on $g(r)$. The idea is simple: We construct a family of instances in which a very large number of demand points arrive at each point in the metric space. This way, the best approach is to open a facility at each point in the metric space. Hence, on these instances, larger $g(r)$ provides better performance. 

\begin{theorem}\label{thm:f_lower_bound}
For all $\delta \in (0,1)$, there is an infinite sequence of input instances ${\cal I}_{\delta,1},{\cal I}_{\delta,2},\dots$, in a metric spaces with uniform distances of $\delta$, where the competitive-ratio of Algorithm~\ref{alg:rofl_q} on ${\cal I}_{\delta,k}$ approaches $1 + \delta/g(\delta) - \delta$ as $k \rightarrow \infty$.
\end{theorem}

\begin{proof}
Let $\delta \in (0,1)$. In the instance ${\cal I}_{\delta, k}$ the metric space consists of $k$ points $\{c_1,\dots,c_k\}$ where $d(c_i,c_j) = \delta$ for all $1 \leq i < j \leq k$. There are $k^2$ demand points in total, $k$ demand points arrive at each location $c_i$ in the metric space. 
First, observe that $\text{\normalfont OPT} \leq k$ as one can open a facility at each point in the metric space and pay $k$. On the other hand, the algorithm first opens a facility at the location $c_{t_1}$ of the first arriving demand point $v_1$ and pays $1$. Let $c_{t_2},\dots, c_{t_k}$ be the remaining  points in the metric space. Before a facility is opened at $c_{t_j}$, the expected cost that the algorithm pays for each demand point that arrive at $c_{t_j}$ is $g(\delta) \cdot 1 + (1-g(\delta)) \cdot \delta$. Hence, the expected cost that the algorithm pays for serving the demand points at $c_{t_j}$ is $
    \sum_{i=1}^{k} \left( 1 - g(\delta) \right)^{i-1} \left( g(\delta) + (1-g(\delta)) \delta \right) = \left( g(\delta) + (1-g(\delta)) \delta \right) \left( 1- (1-g(\delta))^{k} \right) /g(\delta)$.
Therefore, we get that the competitive-ratio of the algorithm is lower bounded by
\begin{align*}
    \frac{1 + (k-1) \left( g(\delta) + (1-g(\delta)) \delta \right) \left(1- (1-g(\delta))^{k}\right)/ g(\delta)}
    {k},
\end{align*}
which approaches $1 + \delta/g(\delta) - \delta$, as $k$ approaches infinity. 
\end{proof}


Following Theorem~\ref{thm:f_lower_bound}, to improve upon a competitive-ratio of $4$, $g$ must satisfy $1 + \delta/g(\delta) - \delta < 4$ and so $g(\delta) > \delta/(3+\delta) > \delta/4$, for all $\delta \in (0,1)$.

To sum up, we choose $g$ of the form $g(r) = q \cdot r$. We note that to simplify our analysis, we use the continuous function $g(r) = \min\{ q\cdot r, 1\}$ instead of the piecewise function $g(r) = q \cdot r$ for $r \leq 1$ and $g(r) = 1 $ otherwise. This choice has no impact on the competitive-ratio, and the same techniques can be used to analyze the piecewise function and gives the same results. Yet, in practice, it is always better to use the peicewise function. We refer to Algorithm~\ref{alg:rofl_q} with the choice $g(r) = \min\{ q\cdot r, 1\}$ by the name $\rofl$.

From our constructed instances above with the choice $g(r) = q \cdot r$, we get that the competitive-ratio of $\rofl$ is at most $1 + 1/q - \delta$, and since we can choose an arbitrarily small $\delta$, we get the following.

\begin{theorem}
There is an infinite sequence of instances ${\cal I}_{1},{\cal I}_{2},\dots$, where the competitive-ratio of $\rofl$ on ${\cal I}_{k}$ approaches $1+1/q$ as $k \rightarrow \infty$.
\end{theorem}


Also, with the instances from the proof of Theorem~\ref{thm:tight_4}, we get the following result.

\begin{theorem}
There is an infinite sequence of instances ${\cal I}_{1},{\cal I}_{2},\dots$, where the competitive-ratio of $\rofl$ on ${\cal I}_{k}$ approaches $2(1+q)$ as $k \rightarrow \infty$.
\end{theorem}

Together, we have the following corollary.
\begin{corollary}\label{cor:roflq_lower_bound}
The competitive-ratio of $\rofl$ is at least $(1+q)\max\{2,1/q\} - o(1)$.
\end{corollary}


We now move to analyze the performance of $\rofl$.
We use the same notations from Section~\ref{sec:meyerson}, and redefine $p(\ell,u)$ to be compatible with $\rofl$: For a demand $u\in {\CS{U}}$ and online round $\ell \in [n]$, let $p(\ell,u) = \min\{q \cdot r(\ell,u), 1\}$. Note that $p(\ell,u)$ is exactly the probability of Heads in line~\ref{line:roflq_heads} of Algorithm~\ref{alg:rofl_q} with $g(r) = \min\{q\cdot r,1\}$ when $v_\ell = u$ (also note that for $q=1$, $p(\ell,u)$ coincides with our original definition for $\rofl[]$). Except for the definition of $p(\ell,u)$, our definition of the analysis' coin as well as the distinction between a balanced and imbalanced opening of a facility remain the same as in Section~\ref{sec:meyerson}.

Our analysis for $\rofl$ is similar to our analysis of $\rofl[]$ in Section~\ref{sec:meyerson}, therefore, we refer to our analysis of $\rofl[]$ when the details remain the same and apply to $\rofl$, and prove analogues lemmas for $\rofl$ when it is required.

We bound the cost of $\rofl$ on each cluster of $\text{\normalfont OPT}$ separately. Consider a cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$ with center ${c^*}$. Recall that for $\ell \in [n]$, $\cpoints{\ell} \subseteq {\CS{C}^*}$ is the set of the remaining demand points $u \in {\CS{C}^*}$ at round $\ell$, and that $T$ is the online round in which the first balanced facility from ${\CS{C}^*}$ is opened.  We partition ${\CS{C}^*}$ in exactly the same way we did in the analysis of $\rofl[]$, that is, ${\CS{C}^*} =  \uptocpoints{T} \cup \cpoints{T+1}$.

We begin by proving an analogue of Lemma~\ref{lem:price_factor}.
\begin{lemma}\label{lem:price_factor_roflq}
The expected cost of $\rofl$ on a demand $u$ is at most $(1+1/q) \cdot \E{p(u)}$
\end{lemma}

\begin{proof}
Fix $u \in {\CS{U}}$. Let $\text{\normalfont ALG}(u)$ be the cost that $\rofl$ pays for serving $u$. Let $p \in [0,1]$. Conditioned on $p(u) = p$, if $p = 1$, the algorithm open a facility at $u$ and pays $1 \leq (1+1/q)$. Otherwise, $p < 1$ and so $p(u) = q \cdot r$ for some $r < 1/q$. $\rofl$ opens a facility at $u$ with probability $q \cdot r$ and pays $1$, and with probability $(1-q)r$, it serves $u$ through an open facility at distance $r$ and pays $r$. Hence, $\E{\@ifstar\@giventhatstar\@giventhatnostar{\text{\normalfont ALG}(u)}{p(u) = p}} = q \cdot r \cdot 1 + (1- q \cdot r) r = q \cdot r + r - q \cdot r^2 \leq (1+q)r = (1+1/q)p$. The lemma follows by taking the expectation over $p(u)$.
\end{proof} 


To bound the cost of $\rofl$ on $\cpoints{T+1}$, we note that Lemma~\ref{lem:C_Tplus1} and Lemma~\ref{lem:exp_v_T} from Section~\ref{sec:meyerson} also apply to $\rofl$. With the new definition of $p(u)$, we have for all $u \in \CS{U}$ that $p(u) \leq q \cdot r(u)$, so we get the following corollary of Lemma~\ref{lem:C_Tplus1} (analogously to Corollary~\ref{cor:C_Tplus1}).
\begin{corollary}\label{cor:C_Tplus1_roflq}
$\E{\sum_{u \in \cpoints{T+1}} p(u)} \leq q \cdot \E{ \sum_{u \in \cpoints{T}} d^*_u} + q \cdot \E{(|\cpoints{T}| - 2)d^*_{v_T}}$.
\end{corollary}

It remains to derive bounds for the demand points in $\uptocpoints{T}$. To this end, we prove an analogue of Lemma~\ref{lem:until_opening}.

\begin{lemma}\label{lem:roflq_until_opening}
$\E{\sum_{u \in \uptocpoints{T}} p(u)} \leq 1 + 2q \cdot  \E{\sum_{u \in \uptocpoints{T}} d^*_{u}}$
\end{lemma} 

\begin{proof}
The proof is very similar to the proof of Lemma~\ref{lem:until_opening}. We use the same definitions and notations as in the proof of Lemma~\ref{lem:until_opening}, except for the new definition of $p_{\CS{F}}(\ell,u) = \min\{q \cdot r_{\CS{F}}(\ell,u), 1\}$ (instead of $\min\{r_{\CS{F}}(\ell,u), 1\}$). With this value of $p_{\CS{F}}(\ell,u)$, we prove a more general inductive statement. 


Recall that for $1\leq \ell \leq n$, $T_\ell \geq \ell$ is the first online round (from round $\ell$ onward) in which a balanced facility is opened by the algorithm, $\tcpoints{\ell} = \{v_\ell,\dots,v_{T_\ell}\} \cap {\CS{C}^*}$, and $P_\ell = \sum_{u \in \tcpoints{\ell}}p(u)$. We prove by downwards induction on $\ell$ that for any $\CS{F} \subseteq {\CS{U}}$ and any sub-sequence of the demand points $\mathbf{x}_{\ell-1} = (x_1,\dots,x_{\ell-1})$ such that $\Pr[\bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}] \neq 0$, it holds that $\E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{\bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}}} \leq 1+ 2q\E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}}{ \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1} ,F_{\ell-1} = \CS{F}} } $.


For $\ell = n$, we have
$P_n = p(v_n)$ if $v_n \in {\CS{C}^*}$ and $0$ otherwise. Since $p(v_n) \leq 1$, the base case of the induction holds. For $\ell < n$, the proof proceeds as in the proof of Lemma~\ref{lem:until_opening}, until we get to  Equation~\eqref{eq:p_l_explained}. Now, similarly to Inequality~\eqref{eq:exp_round_l_2}, we substitute the probabilities with their respective values and use the new induction hypothesis to obtain that
\begin{align}
\begin{split}
    & \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{ 
        \begin{array}{c}
            v_{\ell} = u_j,\\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1},\\
            F_{\ell-1} = \CS{F}
        \end{array}
        }
    } \\
    & \quad \leq p_{\CS{F}}(\ell, u_j) + \left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right) \left(1 + 2 q \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u} }{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array} } }\right) \\
    & \quad \quad +\left(1-  p_{\CS{F}}(\ell, u_j)\right) \left( 1+ 2q \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}}{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array} }
        } \right) \\
    & \quad = 1 + \left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)  \\
    & \quad \quad + 2q\left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)  \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u} }{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u_j\}
            \end{array} } } \\
    & \quad \quad   + 2q\left(1-  p_{\CS{F}}(\ell, u_j)\right) \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}}{
            \begin{array}{c}
                 v_\ell = u_j, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array} }
        }.
\end{split}\label{eq:step2_roflq}
\end{align}

We now upper bound the term $\left(p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j)\right)$. To this end we use Inequality~\eqref{eq:triangle_dist} (which still holds), and show that $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \leq q ( r_{\CS{F}}(\ell, u_j) - r_{\CS{F}}(\ell, w_j))$. Recall that $r_{\CS{F}}(\ell, u_j) \geq r_{\CS{F}}(\ell, w_j)$, $p_{\CS{F}}(\ell, u_j) = \min\{q\cdot r_{\CS{F}}(\ell, u_j),1\}$ and $p_{\CS{F}}(\ell, w_j) = \min\{q \cdot r_{\CS{F}}(\ell, w_j),1\}$. We distinguish between the following cases: If both $q \cdot r_{\CS{F}}(\ell, u_j) \leq 1$ and $q \cdot r_{\CS{F}}(\ell, w_j) \leq 1$, then  $p_{\CS{F}}(\ell, u_j) = q \cdot r_{\CS{F}}(\ell, u_j)$ and $p_{\CS{F}}(\ell, w_j) = q \cdot r_{\CS{F}}(\ell, w_j)$ and the claim holds. If both $q \cdot r_{\CS{F}}(\ell, u_j) > 1$ and $q \cdot r_{\CS{F}}(\ell, w_j) > 1$ then $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) = 0 \leq q \cdot r_{\CS{F}}(\ell, u_j) - q \cdot r_{\CS{F}}(\ell, w_j)$. Finally, if $q \cdot r_{\CS{F}}(\ell, u_j) > 1$ and $q \cdot  r_{\CS{F}}(\ell, w_j) \leq 1$, then  $p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) = 1 - q \cdot r_{\CS{F}}(\ell, w_j) <  q \cdot r_{\CS{F}}(\ell, u_j) - q \cdot r_{\CS{F}}(\ell, w_j)$. Hence, we obtain 
\begin{align}
    p_{\CS{F}}(\ell, u_j) - p_{\CS{F}}(\ell, w_j) \leq  2q  d^*_{u_j}.\label{eq:triangle_roflq}
\end{align}
To conclude, we substitute Inequality~\eqref{eq:triangle_roflq} and use Equation~\eqref{eq:exp_sum_dist} (which still holds) in Inequality~\eqref{eq:step2_roflq}, and get that 
\begin{align}
\begin{split}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell} { 
        \begin{array}{c}
            v_\ell = u_j, \\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
            F_{\ell} = \CS{F}
        \end{array}
        } 
    } 
    &\leq 1 + 2q  \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {        \begin{array}{c}
            v_\ell = u_j, \\
            \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
            F_{\ell} = \CS{F}
        \end{array}
        }}.
\end{split}
\end{align}


For $v_\ell = u \in \CS{U} \setminus \CS{Y}$, similarly to Inequality~\eqref{eq:not_in_C} (with our new induction hypothesis) we also get that
\begin{align*}
\begin{split}
    \E{\@ifstar\@giventhatstar\@giventhatnostar{P_\ell}{\begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}}} 
    &= p_{\CS{F}}(\ell, u) 
        \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}} { 
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u \}
            \end{array}}} 
        + (1-p_{\CS{F}}(\ell, u)) 
        \E{\@ifstar\@giventhatstar\@giventhatnostar{P_{\ell+1}}{
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
        }} \\
    &\leq 1 + 2 q \cdot p_{\CS{F}}(\ell, u) 
        \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F} \cup \{u \}
            \end{array}
        }} \\
    & \quad + 2  q\cdot (1-p_{\CS{F}}(\ell, u)) \E{ \@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell+1}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    }} \\
    &\leq 1 + 2 q\cdot \E{\@ifstar\@giventhatstar\@giventhatnostar{\sum_{u \in \tcpoints{\ell}} d^*_{u}} {
            \begin{array}{c}
                 v_\ell = u, \\
                 \bm{v}_{\ell-1} = \mathbf{x}_{\ell-1}, \\
                 F_{\ell} = \CS{F}
            \end{array}
    } },
\end{split}
\end{align*}
where in the last inequality we used Equation~\eqref{eq:notinc_expression}.
To conclude the inductive argument we take the expectation over $v_\ell$.
\end{proof}

We can now put all the pieces together and derive the competitive-ratio of $\rofl$.

\begin{theorem}\label{thm:qrofl-competitive}
$\rofl$ is $(1+q)\max\{2,1/q\}$-competitive.
\end{theorem}
\begin{proof} 
Similarly to the proof of Theorem~\ref{thm:cr_meyerson},
for a cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$, we have ${\CS{C}^*} =  \uptocpoints{T} \cup \cpoints{T+1} $. By Corollary~\ref{cor:C_Tplus1_roflq} and Lemma~\ref{lem:roflq_until_opening} together with Lemma~\ref{lem:price_factor_roflq}, that
\begin{align*}
\E{\text{\normalfont ALG}\left({\CS{C}^*}\right)} &= \E{\text{\normalfont ALG}\left(\uptocpoints{T}\right)} +  \E{\text{\normalfont ALG}\left(\cpoints{T+1}\right)} \\
&\leq (1+1/q)  \E{\sum_{u \in \uptocpoints{T}} p(u)} + (1+1/q)  \E{\sum_{u \in \cpoints{T+1}} p(u)} \\
&\leq  1+1/q + 2(1+q)\E{\sum_{u \in \uptocpoints{T}} d^*_{u}} +  (1+q) \E{ \sum_{u \in \cpoints{T}} d^*_u} +  (1+q) \E{(|\cpoints{T}| - 2)d^*_{v_T}} \\
&= 1+1/q + 2(1+q)   \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}}  + 2(1+q)  \E{d^*_{v_T}} + (1+q)  \E{ \sum_{u \in \cpoints{T}} d^*_u}  \\
&\quad + (1+q)  \E{(|\cpoints{T}| - 2)d^*_{v_T}} \\
&= 1+1/q + 2(1+q)   \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}} + (1+q)  \E{ \sum_{u \in \cpoints{T}} d^*_u}  + (1+q) \E{(|\cpoints{T}|)d^*_{v_T}} \\
&\leq  1+1/q + 2(1+q) \E{\sum_{u \in \uptocpoints{T-1}} d^*_{u}} + (1+q)\E{ \sum_{u \in \cpoints{T}} d^*_u}  + (1+q) \E{\sum_{u \in \cpoints{T}} d^*_{u}} \\
&= 1+1/q + 2(1+q)  \E{\sum_{u \in {\CS{C}^*}} d^*_{u}}.
\end{align*}
Where in the last inequality we used Lemma~\ref{lem:exp_v_T}. Now since $\text{\normalfont OPT}({\CS{C}^*}) = 1 + \sum_{u \in {\CS{C}^*}} d^*_u$, we have $\E{\text{\normalfont ALG}({\CS{C}^*})} / \text{\normalfont OPT}({\CS{C}^*}) \leq \max\{1+1/q,2(1+q)\}$. Since this is true for each cluster ${\CS{C}^*}$ in $\text{\normalfont OPT}$, we get that $\E{\text{\normalfont ALG}}/\text{\normalfont OPT} \leq (1+q)\max\{1/q,2\}$.
\end{proof}

By Corollary~\ref{cor:roflq_lower_bound}, we get that our analysis of $\rofl$ is tight for all $q \in (0,1)$. Optimizing over the choice of $q$, the best competitive-ratio of $\rofl$ is obtained for $q=1/2$, for which we get a competitive-ratio of $3$.

\begin{corollary}
$\rofl[\nicefrac{1}{2}]$ is $3$-competitive.
\end{corollary}
\section{Mixed Adversarial and Random Arrival Order}\label{sec:mixed}

Interestingly, Meyerson's analysis of $\rofl[]$ in~\cite{meyerson2001online} does not fully utilize the random arrival order of the demand points. More concretely, in~\cite{meyerson2001online} the demand points in each cluster of $\text{\normalfont OPT}$ are partitioned into  ``close'' and ``far'' points. The close points are half of the demand points which are closest to the optimal center. The analysis in~\cite{meyerson2001online} proves that $\rofl[]$ is $8$-competitive, regardless of the relative ordering of the close points in each cluster (amongst themselves). It only requires that each far point arrives in a uniformly random position between the close points. This result indicates that $\rofl[]$ is robust to adversarial ordering of the close points within each cluster.

Since our analysis does not rely on Meyerson's partition into close and far points, we can prove a stronger statement regarding the robustness of $\rofl$ to partial adversarial orders. We show that for a parameter $\rho \in (0,1)$, with an additional cost of a factor of at most $(2-\rho)/\rho$ in the competitive-ratio of $\rofl$, our analysis holds even when an arbitrary $(1-\rho)$-fraction of the demand points in each cluster are ordered adversarially, and the remaining demand points are randomly positioned between them.

Formally, for $\rho \in (0,1)$, in the \textit{$\rho$-partial random-order} setting, the following process generates the online sequence:
\begin{enumerate}
\item The adversary chooses an input instance, i.e., a metric space $(\CS{M},d)$ and the multiset of demand points $\CS{U}$. Let $\CS{C}^*_1,\dots,\CS{C}^*_t$ be the clusters in an optimal solution, and let $n_j = |\CS{C}^*_j|$.
\item For each cluster $\CS{C}^*_j$, the adversary chooses a subset $\CS{A}^*_j \subseteq \CS{C}^*_j$ of cardinality $\lfloor (1-\rho)  \cdot n_j \rfloor$ to arrive in adversarial order, and let $\CS{R}^*_j  = \CS{C}^*_j \setminus \CS{A}^*_j$ be the subset of remaining demand points. We call the demand points in $\CS{A}^*_j$ adversarial-order points, and the points in $\CS{R}^*_j$ random-order points.\label{step:2}

\item The adversary orders the demand points in $\cup_{i=1}^{t} \CS{A}^*_i$. Then, for each cluster $\CS{C}^*_j$, the points in $\CS{R}^*_j$ are randomly positioned between the demand points in $\CS{A}^*_j$. That is, the relative position of $u \in \CS{R}^*_j$ among the points in $\CS{A}^*_j$ is chosen uniformly at random. The absolute positions of the demand points in $\cup_{i=1}^{t} \CS{R}^*_i$ are then chosen by the adversary, while keeping the relative order between the demand points in each cluster.
\end{enumerate}

The definition of the competitive-ratio in this setting is standard. An algorithm $\text{\normalfont ALG}$ is called $c$-competitive if for any input instance ${\cal I} = (\CS{M},d,{\CS{U}}, \CS{A}^*_1,\dots,\CS{A}^*_t)$, $\E{\text{\normalfont ALG}({\cal I})} \leq c \cdot \text{\normalfont OPT}$, where the expectation is taken over the random positioning of the random-order demand points $\CS{R}^*_1,\dots,\CS{R}^*_t$, and the internal randomness of the algorithm.

To analyze $\rofl$ in the $\rho$-partial random-order setting, we bound the expected cost of $\rofl$ for the adversarial-order points in terms of the cost for the random-order points. As before, we focus our attention on a single cluster of $\text{\normalfont OPT}$, ${\CS{C}^*}$. The idea is simple: Our analysis from Section~\ref{sec:improve} applies to the random-order demand points $\CS{R}^*$ in the cluster. Then, for each adversarial-order point $u \in \CS{A}^*$, if $u$ arrives after a random-order demand point $u' \in \CS{R}^*$, we can upper bound the distance from $u$ to its closest open facility by $r(u') + d^*_{u'} + d^*_{u}$. Otherwise, if there are no demand points in $\CS{R}^*$ that arrive before $u$, we can simply bound the cost paid for the service of $u$ by $1$.\footnote{We note that to get the upper-bound of $1$ on the service cost, we need to choose the piecewise function $g(r) = q \cdot r$ if $r \leq 1$ and $g(r) = 1$ otherwise, instead of $g(r) = \min\{q\cdot r,1\}$.} We formalize this intuition in the next theorem.

\begin{theorem}\label{thm:rho_parital}
for $\rho \in (0,1)$, $\rofl$ is $ (1+q)\max\{3/\rho - 1,(2/\rho -1)/q\}$-competitive in the $\rho$-partial random-order setting.
\end{theorem} 

\begin{proof}
Let $u_{1},\dots,u_{k}$ be the demand points in $\CS{R}^*$ ordered by their arrival order. We have by Theorem~\ref{thm:qrofl-competitive} that $\E{\text{\normalfont ALG}(\CS{R}^*)} \leq 1 + 1/q + 2 (1+q) \sum_{u\in \CS{R}^*} d^*_u$. For the adversarial-order demand points, we bound $\E{\sum_{u \in \CS{A}^*} p(u)}$ (recall that $p(u) = \min\{ q\cdot r(u),1\}$). We first consider the distance from the optimal center ${c^*}$ to the closest open facility at the online rounds in which adversarial-order demand points arrive. Let $J_{\CS{A}} \subseteq [n]$ be the set of online rounds in which an adversarial demand point from $\CS{A}^*$ arrives, and let $Z \in J_{\CS{A}}$ be a random variable that gets a uniformly random online round in $J_{\CS{A}}$. Randomly positioning the random-order online rounds within the adversarial-order online rounds is equivalent to randomly positioning the adversarial-order online rounds within the random-order online-rounds. Hence, the probability that $Z$ arrives between $u_j$ and $u_{j+1}$ is $1/(k + 1)$, and in this case we have $d(F_{Z-1}, c^*) \leq r(u_j) + d^*_{u_j}$, and so, $\min\{q \cdot d(F_{Z-1}, c^*),1\} \leq \min\{q\cdot r(u_j),1\} + q\cdot d^*_{u_j} = p(u_j) + q\cdot d^*_{u_j}$. We get that 
\begin{align*}
    \E{\min\{q\cdot d(F_{Z-1}, c^*),1\}} \leq \frac{1}{k+1} + \frac{1}{k+1} \sum_{j=1}^{k} \left( \E{ p(u_j)} + q\cdot d^*_{u_j}\right).
\end{align*}
Now, we can simply upper bound $r(v_\ell) \leq d(F_{\ell-1},c^*) + d^*_{v_\ell}$, and so,
\begin{align}
    \E{\sum_{u \in \CS{A^*}}p(u)} &= \E{\sum_{u \in \CS{A^*}}\min\{q\cdot r(u),1 \}} \notag \\
    & \leq \E{\sum_{\ell \in J_{A}} \min\{q \cdot (d(F_{\ell-1}, c^*) + d^*_{v_\ell}) ,1 \}}
    \notag \\
    &\leq  \E{\sum_{\ell \in J_{A}} \min\{q \cdot d(F_{\ell-1}, c^*) ,1 \}} + q\sum_{u\in \CS{A}^*} d^*_{u}
    \notag \\
    &\leq 
    |\CS{A^*}| \cdot \left(\frac{1}{k+1} + \frac{1}{k+1} \sum_{j=1}^{k} \left( \E{ p(u_j)} + q\cdot d^*_{u_j}\right) \right) + q \sum_{u \in \CS{A}^*} d^*_u \label{eq:line_robust}\\
    &\leq \left(1/\rho - 1\right) \left(1+  \E{\sum_{u \in \CS{R}^*} p(u) } + q\sum_{u \in {\CS{C}^*}} d^*_u \right), \notag
\end{align}
where in the last inequality, we used the fact that $|\CS{A}^*|/(k+1) = |\CS{A}^*|/(|\CS{R}^*|+1) \leq 1/\rho - 1$.
Now, similarly to Theorem~\ref{thm:qrofl-competitive} we have $ \E{\sum_{u \in \CS{R}^*} p(u) } \leq 1 + 2q \sum_{u \in \CS{R}^*}d^*_u$, together with Lemma~\ref{lem:price_factor_roflq}, we get that $\E{\text{\normalfont ALG}(\CS{A}^*)} \leq (1+1/q)(1/\rho -1)(2 + 3q \sum_{u \in {\CS{C}^*}} d^*_u)$. Finally, we add the cost paid for the service of the points in $\CS{R}^*$, and get that
\begin{align*}
    \E{\text{\normalfont ALG}({\CS{C}^*})} &= \E{\text{\normalfont ALG}(\CS{A}^*)} + \E{\text{\normalfont ALG}(\CS{R}^*)} \\ 
    &\leq 
    \left(1+\frac{1}{q}\right)\left(\frac{1}{\rho} -1\right)\left(2 + 3q \sum_{u \in {\CS{C}^*}} d^*_u\right) + 1 + \frac{1}{q} + 2 (1+q) \sum_{u\in \CS{R}^*} d^*_u \\
    &\leq \left(1+\frac{1}{q}\right)\left(\frac{2}{\rho} -1\right) + (1+q)\left( \frac{3}{\rho} - 1\right) \sum_{u\in {\CS{C}^*}} d^*_u.\qedhere
\end{align*}
\end{proof}

We note that in a similar setting, where the adversarial-order demand points are not chosen by the adversary, but rather drawn randomly, we can obtain a better upper bound on the performance of $\rofl$. 

More formally, consider Step~\ref{step:2} in the random process that generates the online sequence in the $\rho$-partial random-order setting, and consider the case where for all $j\in [t]$, $A^*_j \subseteq \CS{C}^*_j$ is a uniformly random subset of cardinality $\lfloor (1-\rho) n_j \rfloor$ (instead of an adversarially chosen subset of the same cardinality), and $R^*_j = \CS{C}^* \setminus A^*_j$. We refer to this setting by \textit{$\rho$-partial random-order with random adversarial-order points}. With small adaptations in the proof of Theorem~\ref{thm:rho_parital}, and by using the fact that in this setting $\E{\sum_{u \in R^*} d^*_u} = \frac{|R^*|}{|{\CS{C}^*}|} \sum_{u \in {\CS{C}^*}} d^*_u $ and $\E{\sum_{u \in A^*} d^*_u} = \frac{|A^*|}{|{\CS{C}^*}|} \sum_{u \in {\CS{C}^*}} d^*_u $ we get the following result.

\begin{theorem}\label{thm:rho_partial_random}
for $\rho \in (0,1)$, $\rofl$ is $ (1+q)\max\{4-2\rho,(2/\rho -1)/q\}$-competitive in the $\rho$-partial random-order setting with random adversarial-order points.
\end{theorem} 

The proof of Theorem~\ref{thm:rho_partial_random} is given in Appendix~\ref{proof:rho_partial_random}. For example, Theorem~\ref{thm:rho_partial_random} shows that $\rofl[]$ is $6$-competitive when a random half of the demand points in each cluster arrive in adversarial order. For comparison, if half of the demand points in each cluster are chosen adversarially, the upper bound that we get from Theorem~\ref{thm:rho_parital} on the competitive-ratio of $\rofl[]$ is only $10$.


\subsection{Organization of the paper}
In Section~\ref{sec:def} we give a formal definition of the online facility location problem in the random-order model and establish notations.
In Section~\ref{sec:meyerson} we present our tight analysis of $\rofl[]$ in the random-order model.
In Section~\ref{sec:improve}, we introduce our generic version of $\rofl[]$, and present tight bounds on its performance.
In Section~\ref{sec:hardness} we prove the hardness result for any algorithm for online facility location in the $\text{i.i.d.}$ model. In Section~\ref{sec:mixed} we introduce the setting of partial adversarial arrival order, and prove a robustness result for our considered algorithms in this setting. Finally, we conclude and discuss open questions in Section~\ref{sec:discussion}.
\section{Problem Definition}\label{sec:def}

In the (metric, uncapacitated) facility location problem, we are given a metric space $(\CS{M},d)$ where $\CS{M}$ is the set of points, and $d : \CS{M} \times \CS{M} \rightarrow \mathbb{R}_{\geq 0}$ is a non-negative and symmetric distance function that satisfies the triangle inequality. We are also given a multiset of demand points ${\CS{U}}$ in $\CS{M}$, and a facility opening cost $f \in \mathbb{R}_{\geq 0}$ (uniform facility cost). 

Each demand must be assigned to an open facility. A facility can be opened at any point in the metric space for a cost of $f$. For $\CS{F} \subseteq \CS{M}$ and $v \in \CS{M}$, $d(\CS{F},v)$ is the minimal distance between a point in $\CS{F}$ and $v$, that is, $d(\CS{F},v) = \min_{u \in \CS{F}} d(u,v)$.\footnote{We define $d(\emptyset,v) = \infty$.} Given a set of open facilities $\CS{F} \subseteq \CS{M}$, the cost of assigning a demand $v$ is $d(\CS{F},v)$. The goal is to find a set of facilities $\CS{F} \subseteq \CS{M}$ that minimizes the total cost $|\CS{F}| \cdot f + \sum_{v\in {\CS{U}}} d(\CS{F},v)$. By scaling, we assume throughout this paper, without loss of generality, that $f=1$.

In the online version of the problem, the demands in ${\CS{U}}$ arrive one by one. Let $v_1,\dots,v_n$ denote the input sequence. The arrival order is determined by the online model, which we specify thereafter. When a demand point $v_\ell$ arrives, the online algorithm must decide immediately, whether and where to open new facilities. Then, $v_\ell$ is irrevocably assigned to its nearest open facility. Let $F_\ell$ be the set of all facilities that the algorithm opens by the end of online round $\ell \in [n]$.\footnote{Note that $F_\ell$ may be a random variable.} The algorithm's \textit{service cost} for $v_\ell$ is the cost incurred by the algorithm at online round $\ell$, i.e., the facility opening cost and the assignment cost, $(|F_{\ell}| - |F_{\ell-1}|) +  d(F_\ell,v_\ell)$. The total cost incurred by the algorithm is given by $|F_n| + \sum_{\ell=1}^n d(F_\ell,v_\ell)$.


In the online random-order model, the input sequence $v_1,\dots,v_n$ is a uniformly random permutation of the demand points in ${\CS{U}}$.\footnote{We note that in contrast to other problems in the random-order model, we do not need to assume that $n$ is known to the online algorithm.}
For an algorithm $\text{\normalfont ALG}$ and an input instance ${\cal I} = (\CS{M},d,{\CS{U}})$, let $\text{\normalfont ALG}({\cal I})$ be the random variable that gets the total cost incurred by the algorithm on ${\cal I}$, and let $\text{\normalfont OPT}({\cal I})$ be the cost of an optimal solution. Also, for a multiset of demand points $\CS{X} \subseteq {\CS{U}}$, let $\text{\normalfont ALG}(\CS{X})$ be the random variable that gets the total service cost of the algorithm for the demand points in $\CS{X}$ (i.e., the cost that the algorithm pays at the online rounds when the demand points from $\CS{X}$ arrive).


With a slight abuse of notation, we also use $\text{\normalfont OPT}({\cal I})$ to refer to the optimal solution as a family of clusters, where a cluster is a  multiset of demand points that are assigned to the same facility.\footnote{In case of multiple optimal solutions, we break ties arbitrarily.} We also refer to the facility of a cluster by the name center. When $\mathcal{I}$ is clear from the context, we omit it from the notation and write $\text{\normalfont OPT}$ instead of $\text{\normalfont OPT}(\mathcal{I})$.

An algorithm $\text{\normalfont ALG}$ is called $c$-competitive in the random-order model, if for any input instance ${\cal I}$, $\E{\text{\normalfont ALG}({\cal I})} \leq c \cdot \text{\normalfont OPT}$, where the expectation is taken over the random arrival order of the demand points, and the internal randomness of $\text{\normalfont ALG}$.

\subsection{Additional Related Work}
In recent years, the random-order model has been widely adopted for the design and analysis of online algorithms for various online problems. Some recent examples are the set cover problem~\cite{gupta2022random}, edge coloring~\cite{bhattacharya2021online, bahmani2012online}, weighted bipartite matching, and various other packing problems that generalize the classical secretary problem~\cite{DBLP:conf/esa/KesselheimRTV13, kesselheim2018primal, kaplan2022online, korula2009algorithms, FeldmanSZ18, albers2021improved}. See also the survey by Gupta and Singla~\cite{gupta2021random} and references therein. 

Following the seminal paper by Meyerson~\cite{meyerson2001online}, the online facility location problem was mostly considered in the standard worst-case adversarial-order model. In~\cite{fotakis2003competitive}, Fotakis gave a lower bound of $\Omega(\log{n}/\log{\log{n}})$, 
and noted that $\rofl[]$ achieves this bound. Fotakis also presented a deterministic $O(\log{n}/\log\log{n})$-competitive algorithm. Anagnostopoulos et al.~\cite{anagnostopoulos2004simple} presented a simpler and more computationally efficient deterministic online algorithm, that achieves a worst-case competitive-ratio of $O(\log{n})$ for Euclidean spaces of constant dimension. On the other hand, their algorithm is not constant competitive in the random-order model.

In~\cite{fotakis2007primal}, Fotakis presented a simple deterministic $O(\log{n})$-competitive algorithm for the online facility location problem which is guided by the dual of an LP relaxation for the problem. Later, Nagarajan and Williamson~\cite{nagarajan2013offline} presented an elegant dual-fitting analysis of Fotakis' algorithm which also proves a competitive-ratio of $O(\log{n})$. They adapted Fotakis' algorithm to the more general online facility leasing problem. For other variants of the facility location problem see the survey by Fotakis~\cite{fotakis2011online}. More recently, Cygan et al.~\cite{cygan2018online} modified $\rofl[]$ to a setting in which demand points may depart.

The facility location problem has received much recent attention in online settings with predictions~\cite{fotakis2021learning, jiang2021online,azar2022online,almanza2021online}. For instance, in~\cite{fotakis2021learning, jiang2021online}, upon the arrival of a demand point, the algorithm receives a prediction on the facility that the demand point is assigned to in the optimal solution. 
The goal is to have an algorithm that uses the predictions, and obtains a performance guarantee that depends on the prediction error: It should be better than the best online worst-case performance guarantee when the predictions are accurate, and close to it when the predictions are erroneous. The works in~\cite{fotakis2021learning, jiang2021online,azar2022online,almanza2021online} achieve this goal with different prediction types and different performance guarantees. We note that the algorithms in~\cite{jiang2021online, fotakis2021learning, almanza2021online} are based on Meyerson's algorithm. 
