# Online Facility Location in Evolving Metrics
## 4 Switching cost  
Finally, we show that every step that incurs a fractional switching cost of \(d\) in a connection variable \(x_{ij}\) incurs an expected increase of at most \(\frac{d}{d+1}\) in the randomized solution. Thus, the expected number of new connections is \(O(1)\).  
Proof.: We break down the total movement from time \(t-1\) to \(t\) in the fractional solution into \(m\times n\) intermediate steps, on each of which only the value of exactly one \(x_{ij}\) is changed. We take first all the \(x_{ij}\)'s whose value increases and then all the \(x_{ij}\)'s whose value decreases, thus managing to preserve a feasible solution in all the intermediate steps. This way, the total switching cost from time \(t-1\) to time \(t\) of the fractional solution does not change while the integral switching cost could only increase due to possible changes in the intermediate steps. First, we will prove the bound in the case the connection variable decreases: \(x_{ij}^{t}=x_{ij}^{t-1}-d\). Let \(Y_{ij}=\min_{i^{\prime}\
eq i}\frac{Z_{ij}}{x_{ij}^{t-1}-d}\), where \(Y_{ij}\sim\exp(\lambda)\) for \(\lambda=1-x_{ij}^{t}\). When the value of \(x_{ij}\) decreases, the value of \(\frac{Z_{ij}}{x_{ij}}\) increases. Therefore, connection \(ij\) cannot be chosen a time \(t\) if is not chosen at time \(t-1\). However, due to the increase of \(\frac{Z_{ij}}{x_{ij}}\), another connection could turn minimal that had not been chosen in the previous time step. This is the only case, when a switching cost is incurred. The probability of this event is bounded by:  
\[\Pr\left[\frac{Z_{ij}}{x_{ij}^{t-1}}\leq Y_{ij}\leq\frac{Z_{ij}}{x_{ij}^{t-1}- d}\right]=F_{Y_{ij}}[\infty]-F_{Y_{ij}}[0]=\frac{\lambda}{x_{ij}^{t-1}-d+ \lambda}-\frac{\lambda}{x_{ij}^{t-1}+\lambda}\]  
This expression is maximized when \(x_{ij}^{t-1}-d=0,\lambda=1\), and therefore is less than  
\[1-\frac{1}{d+1}=\frac{d}{d+1}\]  
Now, we turn to the case where \(x_{ij}^{t}=x_{ij}^{t-1}+d\). When \(x_{ij}\) increases, the ratio \(\frac{Z_{ij}}{x_{ij}}\) decreases. Therefore, if facility \(i\) was chosen in the previous step, it will be chosen again in this step, thus not incurring switching cost. If facility was not chosen in the previous step, it will be chosen in this step with probability  
\[\Pr\left[\frac{Z_{ij}}{x_{ij}^{t-1}+d}\leq Y_{ij}\leq\frac{Z_{ij}}{x_{ij}^{t-1 }}\right]\]  
which is no more than \(\frac{d}{d+1}\), following the exact same analysis with the case of the decreasing connection variables.  
Finally, it is easy to provide the proof of Theorem 4.2, which concludes this section.  
Proof of Theorem 2.: First, notice that, by Lemma 3, the fractional solution of Algorithm 1 is optimal with respect to the facility and connection cost. Therefore, Algorithm 2 will round the solution to an integral one only losing a factor of \(O(\log n)\) in the facility cost and a factor \(O(1)\) in the connection cost, thus being \(O(\log n)\) competitive with the optimal offline solution. Regarding the switching cost, by Lemma 2, the fractional solution is \(O(\log m)\) competitive with the fractional solution. The cost of this solution will only increase by a factor of \(O(1)\) after the randomized rounding, thus proving the result.