# Online Facility Location in Evolving Metrics
## 3 Lower Bounds  
In this section, we prove lower bounds of deterministic and randomized algorithms for ODFL. In both cases, the metric space is a star graph with a client lying on the center of the star for all rounds.  
The core idea of the proofs is to force the online algorithm to pay the switching cost at each round. By carefully selecting the parameters of ODFL, we can prove that any deterministic online algorithm is \(O(m)\)-competitive. For the randomized lower bound, we use [PERSON]'s principle (see examples in Chapter 8 in [11]). Specifically, we choose a randomized instance such that the expected performance of any deterministic algorithm against the optimal offline algorithm is \(\Omega(\log m)\). By [PERSON]'s principle, any randomized algorithm has the same lower bound.  
Proof: Let OPT denote the optimal cost and ALG denote the cost of an online algorithm. The instance consists of a star graph with \(m\) edges and the number of rounds is \(T=m\). Facilities can only be opened in the leaves (a total of \(m\) leaves), and there is one client (\(n=1\)) sitting at the center of a graph for all rounds. The distance of every leaf \(j\) to the  
Figure 1: (**a**) The linear program P for dffline Dynamic Facility Location. (**b**) The dual D of the linear program P.  
center is initially \(d_{j}=d\). Then, the adversary has the following simple strategy at each round \(1\leq t\leq T-1\):  
For every leaf \(j\), such that the online algorithm connects the client to the facility in \(j\), \(d_{j}\) becomes arbitrarily large. At round \(T\), the distances remain the same as in the previous round.  
Observe that there is only one leaf with distance \(d\) from the center of a star for all rounds. The optimal offline solution just opens a facility at this leaf and connects the client to it for all rounds, thus paying \(g+Tf+Td\). On the other side, any competitive online algorithm will prefer to open a new facility at distance \(d\) and connect the client to this facility at the start of each round instead of paying the large distance. Therefore, the cost incurred by any online algorithm is at least \(Tg+Tf+Td\). By setting \(g\gg d=f\), we have that  
\[\frac{\text{ALG}}{\text{OPT}}\geq\frac{Tg+Tf+Td}{g+Tf+Td}=\Omega(T)=\Omega(m)\]  
Turning to the randomized case, the instance consists of the same metric as the deterministic case and the only difference is that we will use randomized adversarial requests. Then, by showing that any deterministic algorithm has a competitive ratio of at least \(\log m\) and by [PERSON]'s principle, we will prove the lower bound for randomized algorithms.  
Now, the adversary chooses uniformly at random an edge \(e\), which has length \(d\) (has not yet become arbitrarily large) at each round \(1\leq t\leq T-1\) and makes its length arbitrarily large. At round \(T\), where only one leaf has distance \(d\), the distances remain the same as in the previous round. Again, the optimal solution uses the leaf in distance \(d\) at all rounds and pays \(g+Tf+Td\). However, the expected switching cost of any competitive algorithm is:  
\[\mathbb{E}[\text{switching cost}]=g+\sum_{t=1}^{T-1}\Pr[\text{ switches at round }t]\cdot g=g+\sum_{t=1}^{T-1}\frac{1}{m-t+1}\cdot g>H_{T}\cdot g\]  
since at each round \(t\) the edge that the algorithm uses becomes arbitrarily large with probability \(1/(m-t+1)\). By setting \(g>Td=Tf\),  
\[\frac{\mathbb{E}[\text{ALG}]}{\text{OPT}}\geq\frac{g\cdot H_{T}+Tf+Td}{g+Tf+Td }=\Omega(\log T)=\Omega(\log m).\]  
This concludes this section with the lower bounds. In the following sections, we present a randomized algorithm for the ODFL problem with a nearly matching bound of \(O(\log m+\log n)\).