  In this paper we study three previously unstudied variants of the online
Facility Location problem, considering an intrinsic scenario when the clients
and facilities are not only allowed to arrive to the system, but they can also
depart at any moment.
  We begin with the study of a natural fully-dynamic online uncapacitated model
where clients can be both added and removed. When a client arrives, then it has
to be assigned either to an existing facility or to a new facility opened at
the client's location. However, when a client who has been also one of the open
facilities is to be removed, then our model has to allow to reconnect all
clients that have been connected to that removed facility. In this model, we
present an optimal O(log n_act / log log n_act)-competitive algorithm, where
n_act is the number of active clients at the end of the input sequence.
  Next, we turn our attention to the capacitated Facility Location problem. We
first note that if no deletions are allowed, then one can achieve an optimal
competitive ratio of O(log n/ log log n), where n is the length of the
sequence. However, when deletions are allowed, the capacitated version of the
problem is significantly more challenging than the uncapacitated one. We show
that still, using a more sophisticated algorithmic approach, one can obtain an
online O(log m + log c log n)-competitive algorithm for the capacitated
Facility Location problem in the fully dynamic model, where m is number of
points in the input metric and c is the capacity of any open facility.
