# Online Facility Location in Evolving Metrics
## 2 Results  
In this work, we study the competitive ratio of ODFL. We start by proving lower bounds for deterministic and randomized algorithms for ODFL. Our first result is the following.  
Theorem 1: _The competitive ratio of any deterministic online algorithm is \(\Omega(m)\) and the competitive ratio of any randomized online algorithm against the oblivious adversary is \(\Omega(\log m)\) for the Online Dynamic Facility Location problem, where \(m\) is the number of facilities._  
Our second result is a randomized algorithm, which is \(O(\log m+\log n)\)-competitive. In order to achieve this, we express the offline Dynamic Facility Location problem as a linear program P (Figure 0(a)). Then, we apply the following two algorithms at each round \(t\).  
1. **Algorithm 1 (Regularization algorithm):** It solves a linear program minimizing the objective function of P modified to include a smooth convex regularization term and obtains the fractional solution \(Sol(t)\).
2. **Algorithm 2 (Rounding algorithm)**: It rounds the fractional solution \(Sol(t)\) of Algorithm 1 to an integral solution using competing exponential clocks.  
```
Parameters:\(\epsilon>0\), \(\eta=\ln(1+n/\epsilon)\) Initialization: Set \(y_{i}^{0}=0\)\(\forall i\in[m]\) and \(x_{ij}^{0}=0\)\(\forall i\in[m],j\in[n]\). At each round t: Let \(d_{t}\in\mathbb{R}_{+}^{m\times n}\) be the distance cost vector and let \(S\) be the set of feasible solutions. Solve the following linear program \((\mathrm{P}^{*})\) to obtain the fractional solution \((y^{\prime},x^{t})\):

\[(y^{\prime},x^{t})=\operatorname*{arg\,min}_{(y,x)\in S}\left\{f\sum_{i=1}^{m} y_{i}+\sum_{j=1}^{n}\sum_{i=1}^{m}x_{ij}\cdot d_{t}(i,j)+\frac{1}{\eta}\sum_{j=1}^{n} \sum_{i=1}^{m}\left[\left(\left(x_{ij}+\frac{\epsilon}{n}\right)\ln\frac{x_{ ij}+\frac{\epsilon}{n}}{x_{ij}^{t-1}+\frac{\epsilon}{n}}\right)-x_{ij} \right]\right\}\]
```  
**Algorithm 2** The rounding algorithm  
Algorithm 1 solves online a linear program to produce a fractional solution at each round \(t\) involving the current distance vector \(d_{t}\). This algorithm is essentially the general algorithm presented in [10], which we adapt to ODFL. The performance of the general regularization algorithm is proved by Theorem 1.1 in [10] for the case of time varying covering constraints. Although we follow the same steps to prove the existence of a \(O(\log m)\)-competitive fractional solution for ODFL, where\(m\) is the number of facilities, we must also address the presence of both covering and precedence constraints in ODFL.  
Algorithm 2 is the randomized procedure that rounds the fractional solution provided from Algorithm 1 to an integral solution. Our contribution here is that we use an appropriate rounding which works favorably with Algorithm 1 so as to produce a solution, which is \(O(\log m+\log n)\)-competitive for ODFL. The rounding algorithm makes use of competing exponential clocks, which have been applied in many similar problems like the Dynamic Facility Location problem [9] and the Online Set Cover with a Service Cost problem [10].  
Theorem 2: _There is a randomized algorithm which is \(O(\log m+\log n)\)-competitive for the Online Dynamic Facility Location problem, where \(m\) denotes the number of facility locations and \(n\) denotes the number of clients._  
**Organization.** In Section 3, we present lower bounds on the competitive ratio of deterministic and randomized algorithms for ODFL. Then, we present Algorithm 1 in Section 4 and Algorithm 2 in Section 5 and prove their guarantees in the respective sections.