# Online Facility Location in Evolving Metrics
## 1 Introduction  
The Facility Location problem is an extensively studied combinatorial optimization problem, which has many practical applications. In this problem, we are given a single metric on a set of clients and facilities, where each facility is associated with an opening cost. The goal is to find a set of facility locations that minimize the opening cost for all facilities plus the connection cost for all clients, where a client's connection cost is its distance to the nearest facility. In many natural location and network design settings, client locations are not known in advance. Motivated by this fact, [PERSON]. [1] introduced online facility location problems, where clients arrive one-by-one and must be irrevocably assigned to a facility upon arrival. In practical settings related to online data clustering, new data points arrive and the decision of clustering some data points together should not be regarded as irrevocable [2]. Understanding the dynamics of temporally evolving social or infrastructure networks has been the central question in many applied areas recently. [PERSON] et al. [3] introduced the Dynamic Facility Location problem, which models the temporal aspects of such networks. In this time-dependent variant of Facility Location problem, clients or facilities may change their location over time and the goal is to achieve the best trade-off between the optimal connections of clients to facilities and the stability of solutions between consecutive timesteps. The temporal aspect of the Dynamic Facility Location problem is modeled by\(T\) metrics given on the same set of clients and facilities, each representing the metric at time step \(t\in\{1,\ldots,T\}\). This is the key difference between the classic Facility Location problem, which is solved in a fixed metric space \(M\) that does not develop over time. Therefore, the Dynamic Facility Location is a Facility Location problem in an evolving metric \(M(t)=\{M_{1},\ldots,M_{T}\}\), which changes at each timestep \(t\in\{1,\ldots,T\}\). In this paper, we study the online variant of the Dynamic Facility Location problem, denoted as ODFL, where the metrics on clients and facilities are revealed one by one at each round. The online algorithm must make its decision before the metric of the next round is revealed and without knowing the total number of rounds. This is the key difference between ODFL and the offline variant of Dynamic Facility Location in [3], where the \(T\) metrics are known beforehand. Therefore, ODFL attempts to capture realistic settings, where the input data are revealed piece-by-piece and the algorithm must make its decision before upcoming input pieces are revealed. The online aspect of the problem poses new challenges and precludes many algorithmic techniques used to deal with offline problems. Next, we give a formal definition of ODFL. **Model. ** In Online Dynamic Facility Location, we are given a set of facilities \(F\), \(|F|=m\), a set of clients \(C\), \(|C|=n\), a switching cost \(g\) and a facility opening cost \(f\). At each round \(t\in\{1,\ldots,T\}\), a new metric between clients and facilities is revealed with the form of a \(n\times m\) dimensional vector \(d_{t}\), which has entries corresponding to distances over \(F\times C\). We denote by \(d_{t}(i,j)\) the distance between client \(j\) and facility \(i\) at time \(t\). At each round \(t\), the goal is to find a subset \(A_{t}\subseteq F\) of open facilities and an assignment \(\phi_{t}:C\longrightarrow A_{t}\) of clients to open facilities so as to minimize the objective:  
\[f\sum_{t=1}^{T}|A_{t}|+\sum_{t=1,j\in C}^{T}d_{t}(\phi_{t}(j),j)+g\cdot\sum_{t =1,j\in C}^{T}\mathds{1}\{\phi_{t}(j)\
eq\phi_{t-1}(j)\}\]  
where \(\mathds{1}\{p\}\) is the indicator function of proposition \(p\). The assignment \(\phi_{t}\) of round \(t\) is chosen without knowing the distance vectors \(d_{t+1},\ldots,d_{T}\) of upcoming rounds.