# Online Facility Location in Evolving Metrics
## 4 The Regularization Algorithm  
In this section, we show that the regularization algorithm of [10] can be applied to ODFL and that it produces a fractional solution at each round, which is \(O(\log m)\)-competitive, where \(m\) is the number of facility locations. We will prove the following theorem:  
Theorem 4.1: _The Regularization Algorithm produces an \(O(\log m)\)-competitive fractional solution for the Online Dynamic Facility Location problem, where \(m\) is the number of facilities._  
Before proceeding to the details of Algorithm 1, we first express the offline Dynamic Facility Location as a linear program, denoted as P (Figure 0(a)). Algorithm 1 will solve a linear program P\({}^{*}\) at each round, which will be constructed from P combined with a regularization function. Finally, we will show that the fractional solution of P\({}^{*}\) is \(O(\log m)\)competitive with respect to the solution of the dual program D (Figure 1b) of P, which serves as lower bound on the optimal offline solution. Now, we express offline Dynamic Facility Location as an integer program, which will be relaxed to obtain the linear program P. Recall that \(T,n,m\) are the number of rounds, clients, and facility locations, respectively. The first term of the objective function is the total facility opening cost, where \(f\) is the cost to open a facility. The second term is the total connection cost, where \(d_{t}(i,j)\) is the distance between facility \(i\) and client \(j\) in round \(t\), and the third term is the total switching cost, where each change of a client's connection to a facility costs \(g\). We use the decision variables \(y^{t}_{i}\), \(x^{t}_{ij}\) and \(z^{t}_{ij^{\prime}}\), where \(i\in[m],j\in[n],t\in[T]\); \(y^{t}_{i}=1\) if facility \(i\) is open at round \(t\) and \(y^{t}_{i}=0\) otherwise, \(x^{t}_{ij}=1\) if client \(j\) is connected to facility \(i\) at round \(t\) and \(x^{t}_{ij}=0\), otherwise, \(z^{t}_{ij}=1\) if client \(j\) was connected to facility \(i\) at round \(t\) but not connected to the same facility \(i\) at round \(t-1\) and \(z^{t}_{ij}=0\), otherwise. The value of the variable \(z^{t}_{ij}\) is imposed from the third constraint, which expresses the switching cost. The first constraint (\(x^{t}_{ij}\leq y^{t}_{i}\)) ensures that, whenever a client \(j\) is connected to a facility \(i\), the facility \(i\) is open. The second constraint (\(\sum_{i=1}^{m}x_{ij}\geq 1\)) guarantees that every client is connected to a facility. Finally, relaxing the decision variables to take non-negative real values, we obtain the LP of Figure 1a, denoted as P.  
Next, we are ready to present Algorithm 1. The algorithm is given at each round \(t\) a distance vector \(d_{t}\in\mathbb{R}_{+}^{m\times n}\) containing the distances between clients and facilities. Then, Algorithm 1 finds the minimizer \((y^{t},x^{t})\) of the linear program P\({}^{*}\) at each round \(t\), which has two differences from P. The first one is that the last term of the objective function in P (the switching cost) is substituted by the regularization function in P\({}^{*}\). The second is that the constraint relative to the switching cost (\(z^{t}_{ij}\geq x^{t}_{ij}-x^{t-1}_{ij}\)) in P is omitted in P\({}^{*}\). We note that the regularized objective function includes both the previous solution as well as the current cost vector. Thus, the solution in each round is determined greedily and independently of rounds prior to \(t-1\). To analyze the performance of Algorithm 1, we will need to construct a lower bound on the optimal offline solution.