# Online Facility Location in Evolving Metrics
## 4 The Regularization Algorithm
Therefore, we derive the dual D of P (Figure 1b), which has the following variables (corresponding to the primal constraints on the left):  
* \(x^{t}_{ij}\leq y^{t}_{i}\to e^{t}_{ij}\) for all \(t\in[T]\), \(i\in[m]\), \(j\in[n]\)
* \(\sum_{i=1}^{m}x^{t}_{ij}\geq 1\to a^{t}_{j}\) for all \(t\in[T]\), \(j\in[n]\)
* \(z^{t}_{ij}\geq x^{t}_{ij}-x^{t-1}_{ij}\to b^{t}_{ij}\) for all \(t\in[T]\), \(i\in[m]\), \(j\in[n]\)  
We will prove Theorem 3 by showing that the set of dual variables of the solutions that P\({}^{*}\) returns is a feasible solution for D within a factor of \((1+(1+\epsilon^{\prime})\ln(1+\frac{m}{\epsilon^{\prime}}))\) of the optimal offline solution, where \(\epsilon^{\prime}\) is a small constant. Specifically, we will use the KKT optimality conditions of P\({}^{*}\) (the regularized LP) in each round. The constraints define dual variables, which will be plugged in the formulation of the dual D in Figure 1b. This way, we will construct a dual solution to the original online problem, which will serve as a lower bound on the optimal offline solution. Ref. [10] mentions that their technique can be generalized to facility location problems, without providing any further technical details. In the next lemmas, we verify their claim, by adjusting their approach and proof techniques to ODFL. Recall that the constraint \(z^{t}_{ij}\geq x^{t}_{ij}-x^{t-1}_{ij}\) is omitted in P\({}^{*}\). In order to define a feasible solution for D, we introduce the variable \(b^{t}_{ij}\) corresponding to this constraint and we let \(e^{*}_{ij},a^{*}_{j}\) be the optimal dual variables of D\({}^{*}\) corresponding to the precedence and covering constraints, respectively. Lemma 1: _The set of optimal solutions for each round \(t\) of the dual LP \(D^{*}\) of \(P^{*}\)\((a^{*,t},e^{*,t})\), which satisfy the KKT conditions for an appropriate \(b^{t}_{ij^{\prime}}\) consist of a feasible solution for D._  
Proof: Let \(x^{*,t}\) be the optimal solution of P\({}^{*}\) at round \(t\). Set the variables of D at time \(t\) to be:\[a_{j}^{t}=a_{j}^{*,t},\ e_{ij}^{t}=e_{ij}^{*,t}\ \text{and}\ b_{ij}^{t+1}=\frac{g}{ \eta}\ln\frac{1+\frac{\epsilon}{n}}{x_{ij}^{*,t}+\frac{\epsilon}{n}}\]  
To prove that the solution above is feasible for D, we prove that it satisfies its constraints one by one. This is achieved using the following KKT conditions that hold for P\({}^{*}\) and its dual:  
\[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\] \[e_{ij}^{*}\geq 0\,\forall i\in[m],\forall j\in[n]\] (2) \[f-\sum_{j=1}^{n}e_{ij}^{*}\geq 0\,\forall i\in[m]\] (3) \[d_{t}(i,j)+\frac{g}{\eta}\ln\frac{x_{ij}^{*}+\frac{\epsilon}{n}}{x_{ ij}^{t-1}+\frac{\epsilon}{n}}+e_{ij}^{*}-a_{j}^{*}\geq 0\,\forall i\in[m],\forall j\in[n] \tag{4}\]  
The first group of constraints of the dual D (Figure 1b) (\(\sum_{j=1}^{n}e_{ij}^{t}\leq f\)) follows easily from KKT condition (3). The same holds for the last two groups of constraints (\(e_{ij}^{t}\geq 0\) and \(a_{j}^{t}\geq 0\)) due to KKT conditions (1) and (2). Furthermore, by (4) and the construction of \(b_{ij}^{t}\) we have that:  
* \(b_{ij}^{t}=\frac{g}{\eta}\ln\frac{1+\frac{\epsilon}{n}}{x_{ij}^{*,t-1}+\frac{ \epsilon}{n}}=\frac{g}{\ln(1+\frac{\epsilon}{2})}\ln\frac{1+\frac{\epsilon}{ \epsilon}}{x_{ij}^{*,t-1}+\frac{\epsilon}{n}}\stackrel{{ x^{*,t}>0}}{{\leq}}\frac{g}{\ln(1+\frac{\epsilon}{2})}\ln \frac{1+\frac{\epsilon}{\epsilon}}{\frac{n}{\epsilon}}=\frac{g}{\ln(\frac{ \epsilon}{2}+1)}\ln(\frac{n}{\epsilon}+1)=g\)
* \(b_{ij}^{t+1}-b_{ij}^{t}=-\frac{g}{\eta}\ln\frac{x_{ij}^{*,t}+\frac{\epsilon}{ n}}{x_{ij}^{*,t-1}+\frac{\epsilon}{n}}\stackrel{{(\ref{eq:b_1})}}{{ \leq}}d_{t}(i,j)+e_{ij}^{t}-a_{j}^{t}\). * \(b_{ij}^{t}=\frac{g}{\eta}\ln\frac{1+\frac{\epsilon}{n}}{x_{ij}^{*,t-1}+\frac{ \epsilon}{n}}\stackrel{{ x^{*,t}<1}}{{\geq}}\frac{g}{\eta}\ln\frac{1+ \frac{\epsilon}{\epsilon}}{1+\frac{\epsilon}{n}}=0\)  
The above inequalities prove that the second, third, and fourth group of constraints of D also hold, thus completing the proof of the lemma.