# Online Facility Location in Evolving Metrics
## 4 The Regularization Algorithm
We are now ready to prove Theorem 3, by showing that the dual we constructed can pay for the facility, connection, and switching cost of Algorithm 1. Since we bound together the facility cost and connection cost, we will simply refer to them as the service cost. Throughout the proofs, we will use the following relations:  
\[a_{j}^{*}(1-\sum_{i=1}^{m}x_{ij}^{*})=0,\ \forall j\in[n] \tag{5}\] \[y_{i}^{*}(f-\sum_{j=1}^{n}e_{ij}^{*})=0,\ \forall i\in[m]\] (6) \[x_{ij}^{*}(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}^{*})=0,\ \forall i\in[m],\forall j\in[m]\] (7) \[e_{ij}^{*}(x_{ij}^{*}-y_{i}^{*})=0,\ \forall j\in[n],\forall i\in[m]\] (8) \[h-k\leq h\ln(h/k)\ \text{for any}\ h,k>0\] (9) \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]0  
Equalities (5)-(8) are the KKT conditions of P\({}^{*}\) and its dual and the remaining two inequalities are standard logarithmic inequalities. Theorem 3 will follow from the next two lemmas. The analysis is similar to that of Theorem 1.1 in [10] adapted to the objective of ODFL and also dealing with the presence of precedence constraints. **Lemma 2**. : _The switching cost \(M\) of Algorithm 1 is at most \(\eta(1+\frac{\epsilon m}{n})\) times the cost of the dual feasible solution of Lemma 1._  
Proof. : Let \(M_{t}\) be the switching cost of Algorithm 1 at round \(t\). The summation below is taken over increasing values of connection variables, i.e., \(x_{ij}^{s,t}>x_{ij}^{s,t-1}\), since decreasing values only decrease the fractional switching cost:  
\[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]1 \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]2 \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]3 (by inequality (9)) \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]4 (by (7)) \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]5 \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]6 (by (5))  
Hence,  
\[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]7  
This concludes the proof of the lemma. **Lemma 3**. : _The total service cost \(S\) of Algorithm 1 is less than the cost of the dual feasible solution of Lemma 1:_  
Proof. : \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]8 \[a_{j}^{*}\geq 0\,\forall j\in[n] \tag{1}\]9 (by (7) and (6)) \[e_{ij}^{*}\geq 0\,\forall i\in[m],\forall j\in[n]\]0 \[e_{ij}^{*}\geq 0\,\forall i\in[m],\forall j\in[n]\]1 (by (8)) \[e_{ij}^{*}\geq 0\,\forall i\in[m],\forall j\in[n]\]2 (by (5)) \[e_{ij}^{*}\geq 0\,\forall i\in[m],\forall j\in[n]\]3 (by (10))  
The rounding algorithm samples independently a total of \(n\cdot m\) (one for each client-facility connection) random variables \(Z_{ij}\) from the exponential distribution with rate \(\lambda=1\) at the beginning of its execution, which will be used throughout all rounds. Then, at each round \(t\), it chooses for each client \(j\) the connection \(\{i,j\}\) minimizing the ratio \(\frac{Z_{ij}}{x_{ij}^{t}}\), where \(x_{ij}^{t}\) is the fractional variable of this connection obtained by Algorithm 1. Notice that, by the properties of Definition 1, the ratio \(\frac{Z_{ij}}{x_{ij}^{t}}\) is also an exponential random variable. This technique is referred to as competing exponential clocks, since a random variable wins the competition if it has the smallest value among all others (minimizes the ratio \(\frac{Z_{ij}}{x_{ij}^{t}}\) in our case). The high level idea of the analysis is that connection and switching cost of the rounded solution add only constant factors to the cost of the connection and switching cost of the fractional solution at each round \(t\). The reason is that they favor connections to facilities that are dependent on the increase/decrease of the fractional variables \(x_{ij}^{t}\). This fact combined with the properties of the exponential distribution leads to a rounding of the _right_ connections indicated by the fractional solution. On the other side, this leads to more open facilities, since we prove that the rounding adds a factor logarithmic in \(n\) to the cost of the fractional solution.