Efficient and Stable Fully Dynamic Facility Location
Authors: Sayan Bhattacharya
Silvio Lattanzi
Nikos Parotsidis
Venue: NeurIPS 2022 Accept (2022)
Keywords: Clustering
Facility Location
Dynamic Algorithms
Consistent
Recourse
Approximation

Abstract: We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining a stable and high quality solution throughout the data stream while using only little time per update (insertion or deletion). We study the problem and provide the first algorithm that at the same time maintains a constant approximation and incurs polylogarithmic amortized recourse per update. We complement our theoretical results with an experimental analysis showing the practical efficiency of our method.

Efficient and Stable Fully Dynamic Facility Location
Sayan Bhattacharya Department of Computer Science University of Warwick Coventry, CV47AL, United Kingdom bhattacharya&wwariitk ac
Silvio Lattanzi Google Research s silviol@google.. com
Nikos Parotsidis Google Research mikosp@google e com
Abstract
We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining stable and high quality solution throughout the data stream while using only little time per update (insertion or deletion). We study the problem and provide the first algorithm that at the same time maintains constant approximation and incurs polylogarithmic amortized recourse update. We complement our thcoretical results with an experimental analysis showing the practical efficiency of our method.
Introduction
Clustering is fundamental problem in unsupervised learning with many practical applications in community detection, spam detection, image segmentation and many others. central problem in this space with a long and rich history in computer science and operations research Korte and Vygen [2018] is the facility location problem(whic) can also seen as the Lagrangian relaxation of the classic k-median clustering). Due to its scientific importance and practical applications the problem has been studied extensively and several approximation algorithms are known for the problem Guha and Khuller [1999], Jain et al. [2003], Li [2013]. In addition, the problem has also been extensively studied various computational model as the streaming model Indyk [2004], Lammersen and Sohler [2008], Czumaj et al. [2013], the online model Meyerson [2001], Fotakis [2008] and dynamic algorithm model Cygan et al. [2018), Goranci et al. [2018], Cohen-Addas al. [2019], Guo et al. [2020] and many more.
Real world applications nowadays often process evolving data-sets, i.c. social networks continuously evolve in time, videos and pictures are constantly uploaded and taken down from media platforms, news article and blog posted are uploaded or taken down and so on so for. For this reason, is important to design algorithms that are able to maintain a stable and high quality solution and that the same time can process updates efficiently. model have been extensively studied and several interesting results are known for classic learning problems Lattanzi and vitsil [2017], Chan er [2018], Cohen-Addad et al. [2019], Jaghargh et al. [2019], Lattanzi et al. [2020], Fichtenberger et al. [2021], Guo et al. [2021]. In this paper, we extend this line of work by studying the classic facility location problem in the fully dynamic setting.
a consequence, the dynamic and online
Problem definition. The input to our problem consists of a collection F of facilities and collection D of clients in a general metric space. For all E F,j E D, we let d,j denote the distance between facility& i and client j'. These distances satisfy triangle inequality. Let fa denote the opening cost of facility i E F. Our goal is to open subset of facilities F' C F and then connect every client j E D some open facility i, E F", as minimise the objective ΣieF fo ESED diy The first sum
For simplicity, we assume that all the distances between facility and client are polynomially bounded.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

in the objective denotes the sum of the opening costs of the facilities in F", whereas the second sum denotes the sum of the connection costs for the clients. Throughout the rest of this paper, we will let y [F] and n = [P] respectively denote the number of facilities and clients.
We consider dynamic setting, where the input to the problem keeps changing via sequence of updates. Each update inserts or deletes a client in the metric space. Throughout this sequence of updates, we wish to maintain an approximately optimal solution the current input instance with small recourse. The recourse of the algorithm is defined as follows. Whenever we open a new facility or close an already open facility, we incur one unit of facility-recourse. Similarly, whenever we reassign a client from one facility to another, we incur one unit of algorithm after an update is the sum of recility- and client-recours Note that the recourse of an algorithm naturally captures the consistency of the solution throughout the input updates. So having small recourse is particularly important for real world application where clustering is served to the user or used in a machine learning pipeline Lattanzi and Vassilvitskii [2017]. Our main result in this paper is summarized in the theorem below.
The recourse of the
Theorem 1. There is a deterministic aaprrxxitannio algorithm fully dynamic facility location problem that has Olog m) amortized recourse, under the natural assumption that the distances between betweenfacilitiee and clients and the facility opening-costs are bounded by some polynomial in m.
Our Technique. To the best of our knowledge, this the first algorithm for fully dynamic facility location that can handle non-uniform facility costs and maintains a (1) approximation with polylog- arithmic recourse per update. To obtain our result, we consider a relaxed version of the natural greedy algorithm in the static setting. This relaxed greedy algorithm proceeds in iterations. In each iteration the algorithm picks cluster, which specifies set of currently unassigned clients and the facility they will get assigned to, that has approximately minimum average marginal cost. The algorithm stops when every client gets assigned to some facility. the dynamic setting, we ensure that the solution maintained by our algorithm always corresponds to an output of the relaxed greedy algorithm (assuming the relaxed-greedy algorithm receives the current input instance). To be a bit more precise, we formulate a set of invariants which capture the workings of the relaxed greedy algorithm, and fix the invariants using a simple heuristic whenever one or more of them get violated in the dynamic setting. The approximation guarantee now follows from the observation that the relaxed greedy algorithm returns a (1) approximation in the static setting. The recourse bound, on the other hand, follows from a careful token- argument that is inspired by the analysis of a fully dynamic greedy algorithm for minimum set cover Gupta et al. [2017]. In addition, using standard data structures it is easy to show that the amortized update time of our algorithm is Ó(m). We note that this update time is near-optimum, as each arriving client needs to reveal its distances to the facilities, which also holds for the uniform facility opening cost as pointed out in Cohen-Addad et al. [2019]2.
We also complement our theoretical analysis with an in-depth study of the performance of our algorithm showing that our algorithm very efficient and effective in practice.
Related Works. Facility location and dynamic algorithms have been extensively studied in the algorithm and machine learning literature. Here we give an overview of closely related results.
Facility Location. The classic offline metric facility location problem has been extensively studied (see Korte and Vygen [2018]). The best-known approximation for the problem algorithm gives 1.488 approximation Li [2013]. The problem is known to be NP-hard, and it cannot be approximated within a factor of 1.463 unless NP C DTTIM((1 logg)))()) Guha and Khuller [1999].
Dynamic algorithm for clustering and facility location. Recently several dynamic algorithms have been introduced for clustering and facility location problems Lattanzi and Vassilvitskii [2017]. Chan et al. [2018], Cygan et al. [2018]. Goranci et al. [2018], Cohen-Addad et al. [2019], Henzinger et al. [2020], Guo al. [2020], Goranci et al. [2021], Fichtenberger al. [2021]. The recourse for clustering problems was studied in Lattanzi and Vassilvitskii [2017], then several papers followed up with interesting results on recourse and dynamic algorithms Chan et al. [2018), Cohen-Addad et al. [2019], Henzinger et al. [2020], Fichtenberger et al. [2021].
Efficient algorithm for the fully-dynamic facility location problem are known either when the doubling dimension of the problem is bounded Goranci et al. [2018. 2021] or when the facility have uniform
In some works, some assumptions on the form of the input are make, which allow avoiding an 32(m) factor. e.g. Guo al. [2020] where each arriving client reports its nearest facility uppon arrival.

---

cost Cygan et al. [2018], Cohen-Addad et al. [2019]. When the facilities can have arbitrary non- uniform costs in a general metric space, prior to our work the best known fully dynamic algorithm achieved Ologg Fl) approximation with polylogarithmic recourse Guo et al. [2020].
2
Our Dynamic Algorithm
In Section 2.1, we present an intuitive overview of our algorithm. We formally describe our algorithm Section 2.2 and Section 2.3, and analyze its recourse and approximation guarantee in Section 2.4.
2.1 An Informal Overview of Our Algorithm
We start by recalling a natural greedy algorithm for the facility location problem in the static setting. This (static) algorithm is known to return a constant approximation for the problem Jain et al. [2003]. The algorithm proceeds in rounds. Throughout the duration of the algorithm, let F S F and D S D respectively denoted the set of opened facilities and the set of clients that are already assigned to some open facility. Initially, before the start of the first round, we set F <- 9 and D + 0. The next paragraph describes what happens during a given round of this algorithm.
Say that a cluster C' is an ordered pair (i, A), where i E F and A C D. A cluster is either satellite critical. If a cluster C = (i, A) is satellite (resp. critical), then its cost is given by cost(C) == Eie di (resp. CCst(C) := Si + +ZjeA diz). Thus, the only difference between an satellite cluster and a critical cluster is that the cost of the former (resp. latter) does not (resp. does) include the opening cost of the concerned facility. The average cost of cluster C = (i, A) is defined as costang (C) = (oo((C//AA)
Let Coral [F+, D be the set of all satellite clusters C = (i, A)
with F and A C D \ D and let Corie (F*, D²)) be the set of all critical clusters C = (i. A)
with i E F F and A C D \ D In the current round, we pick a cluster C = (i, A) E Corit (F" DD) CF", (")) with minimum average cost, set F + F U {i} and D + D* U A. and assign all the clients E A to the facility i. At this point, if D* = D, then we terminate the algorithm. Otherwise, we proceed the next round.
Intuitively, in each round the above greedy algorithm picks a cluster with minimum average cost, which is defined in such way that takes into account the opening cost of a facility the first time some client gets assigned to it. Let C denote the collection of all clusters picked by this algorithm, across all the rounds. Note: (1) Every client) j A belongs exactly one cluster in C. (2) Let C(i) C C denote the subset of clusters in C which contain a given facility i E F. If C(i) # 0. then exactly one of the clusters in C(i) is critical. We refer collection C which satisfy these two properties a clustering. It is easy to check that clustering C defines valid solution to the concerned instance of the facility location problem, where the objective value of the solution is given by obj(C) == -CEcc (Cs)
Note that if the above algorithm picks an satellite cluster C = (i, A) in given round, then w.l.o.g. we can assume that |A| = 1. This is because if |A| >> 1, then we can only decrease the average cost of C by deleting from A all but the one client that is closest to facility i. Accordingly, from now on we will only consider those satellite clusters that have exactly one client.
Our dynamic algorithm is based on a relaxation of the above static greedy algorithm, where in each round we have the flexibility of picking a cluster with approximately minimum average cost. The output of this relaxed greedy algorithm corresponds to what we call a nice clustering (see Section 2.2 for a formal definition). We now present a high-level, informal overview of our dynamic algorithm.
Upon receiving an input (F, D) at preprocessing, we run the relaxed greedy algorithm which returns a nice clustering C. We assign each cluster C' C to (not necessarily positive) integer level ((C) E E such that costavg (C) ( Thus, the level of cluster encodes its average cost upto a constant multiplicative factor. Define the level of a client j E C to be E()) == E(C).
Preprocessing:
Handling an update: When client gets deleted from D, we simply delete the concerned client from the cluster in C it appears in. Similarly, when a client j gets inserted into D. we arbitrarily assign it to any open facility i by creating an satellite cluster (C = (i, {i}) at the minimum possible level k: 2 Ollg d.j). At this point, we check if the clustering C being maintained by our algorithm still remains nice, i.e., whether C can correspond to an output of the relaxed greedy algorithm on the current input. If the answer is yes, then our dynamic algorithm is done with handling the current update. Thus, for the rest of this discussion, assume that the clustering C is no longer nice.
3

---

It turns out that in this event we can always identify a cluster C. = (i, A) (not necessarily part of C) and a level l E Z such that: costavy( v O(2)) and P(j) > k: for all clients j E A. We refer to such cluster C (i, A) as a blocking cluster. Intuitively, the existence of a blocking cluster is a certificate that the current clustering C' is not nice. This is because the relaxed greedy algorithm constructs the levels in bottom-up manner, in increasing order of average costs of the clusters that get added to the solution in successive rounds. Accordingly, the relaxed greedy algorithm would have added the cluster C its solution level < k before proceeding to level + 1, and this contradicts the fact that a client j E A appears at level > k in the current clustering C.
As long there is blocking cluster C (i, A) at some level k; update the current clustering C by calling a subroutine FIx-BI.OcK BL.OCKINGCCCCCCC k:) which works as follows: (1) it adds the cluster C' to level k; and (2) it removes each client j E A from the cluster in C it belonged to prior this step.
Next, note that because of step (2) above, some cluster C" = At', might lose one or more clients j as they move from C" to the newly formed cluster C. and this might increase the average cost of the cluster C", Thus, we might potentially end up in a situation where a cluster C" (i', At) has costarg ( (C)) > 2!(C", As long as this happens to be the case, we call a subroutine FIX-LEVEI whose job increase the level of the affected cluster C" by one.
Our algorithm repeatedly calls the subroutines FIx- (OX-BLOCKING(..) and FIX-LEVEL()) until there no blocking cluster and every cluster E C has costang (C) = (2((C))) At this point, we are guaranteed that the current clustering is nice and are done with processing the concerned update.
The approximation ratio of our algorithm follows from the observation that a nice clustering cor- responds to the output of the relaxed greedy algorithm in the static setting, which in turn gives a apparxppoxiiiioon. We bound the amortized recourse by careful token-based argument.
2.2 Nice clustering
In Section 2.1,
we explained that nice clustering corresponds to an output of the relaxed greedy algorithm in the static setting. We now give a formal definition of this concept by introducing four invariants. Specifically, we define clustering C to be nice iff it satisfies Invariants 1, 2, 3 and 4.
Every cluster C E C is assigned (not necessarily positive) integer level E(C) E Z. For any cluster C' = (i, A) E C and any client) j E A, we define the level of the client to be {(j) :- (C))
Invariant 1. For every cluster C' E C, we have costagy (C) < 2(())
The relaxed greedy algorithm constructs these levels in a "bottom-up up" manner: it assigns the relevant clusters to level l before moving on to level k - 1. This holds because the algorithm picks the clusters in (approximately) increasing order of their average costs. Also, before picking an satellite cluster C = (i, {i}), the algorithm ensures that facility i is open. This leads to the invariant below.
Invariant 2. Consider any facility i E F with C(i) + 0. Then the unique critical cluster C* E C(i)
satisfies: E(C*) S E(C) for all C E C(i).
The next invariant captures the fact that in an output of the relaxed greedy algorithm, if a client j E D gets assigned facility E F then {(j) 2 O(log drj).
Invariant 3. For every cluster C' (i, A) E C and every client j E A, we have E(j) Kig where Kij is the unique level s.t. 2- < dij < 3
Finally, we formulate an invariant which captures the fact that the relaxed greedy algorithm picks the clusters in an (approximately) increasing order of their average costs. Towards this end, we define the notion of blocking cluster, as described below.
Definition 1. Consider any clustering C, any level k E Z, and any cluster C = (i. A) that does not necessarily belong to C. The cluster C is blocking cluster level l w.r.t C iff three conditions hold. (a) We have cost asstagg( (C)) < 2k-3 (b) For every j E A, we have {(j) > k 2 Kig where Kig is the unique level s.I. 2 4 < dij < 2% (c) IfC is an satellite cluster, then there a critical cluster C* C(3) with E(C*) < k. Else C is a critical cluster, then l S E(C') for all C' E C(i).

---

Intuitively, if C = (i. A) is a blocking cluster at level k w.r.t. C, then the relaxed greedy algorithm should have formed the cluster levels which currently contain all the clients in A. This leads us to the invariant below.?
some level k' before proceeding to construct the subsequent
Invariant 4. There no blocking cluster w.r.t. the clustering C at any level k E Z.
Remark. Consider cluster C = (i, A) E C at level E(C) k. If costang (C) < 2 then it is not difficult to show that there exists subset of clients A' S A such that C² (i. A') a blocking cluster at level k - 1. This, along with Invariant I, implies that costavy (C) = ((2(()) for all C' C
The next theorem holds since a nice clustering corresponds to the output of the relaxed greedy algorithm, and since the (original) greedy algorithm is known to have an approximation ratio of O(1). We defer the proof of Theorem 2 to Appendix B.
Theorem Any nice clustering forms a app-apppox optimal solution to the concerned input instance of the facility location problem.
2.3 Description of Our Dynamic Algorithm
In the dynamic setting, we simply maintain a nice clustering. To be more specific, w.l.o.g. we assume that D = @ at preprocessing. Subsequently, during each update, client gets inserted into / deleted from the set D. We now describe how our algorithm handles an update.
Handling the deletion of a client j: Suppose that client belonged to the cluster C = A) E C just before getting deleted. We set A + A \ {i), and then we call the subroutine described in Figure 1.
Handling the insertion of a client j: We identify any open facility E F.+ Let Kiy E Z be the unique level such that 2 -4 < dij < 2 -3, Let C (i, A) be the unique critical cluster with facility i. If Kij I {(C), then we set A + AU. In this case the client becomes part of the critical cluster C' at level ((C). Else if n. > R(C). then we create new satellite cluster (i, (i}) at level E((i, (i})) = Kij. and set C + CU ((i,))) Next, we call the subroutine described in Figure 1.
The subroutine FIx- CL-SSLSSSERI:G)):: The insertion deletion of a client might lead violation of Invariant 4 or Invariant 1 (the procedure described in the preceding two paragraphs ensure that Invariant 2 and Invariant 3 continue to remain satisfied). The subroutine FiX-CI.UTTERINGL, handles this issue. It repeatedly checks whether Invariant 4 or Invariant 1 is violated, and accordingly calls FIX-BILCKKING(: k) or FIX-LEVEI. Each of these last two subroutines has the property that it does not lead to any new violation of Invariant 2 or Invariant 3. Thus, when the WHILE loop in Figure terminates, all the invariants are restored and end up with a nice clustering.
1. WHILE either Invariant 4 Invariant is violated:
2. IF Invariant 4 is violated, THEN
3. Find cluster C (i, A) that is blocking level ie (say).
4. Call the subroutine FiX-BLOCKING(CC k).
5. ELSE IF Invariant 1 is violated, THEN
6. Find a cluster C = (i. A) (say) that violates Invariant 1.
Call the subroutine Fix (Ex-LEVEL(C).
Figure 1: FIX-CLUSTERIING()
The subroutine FIX-BLOCKING(C, k): This subroutine works as follows. We first add the cluster C = (i, A) to the current clustering. Towards this end, we set E(C) k. C + CU(C), and perform the following operations for all clients j E A.
*
Let C -C' A1) be the cluster the client belonged to just before the concerned call to the subroutine Fix- BOX-BLOCKIN((CK.. k). Set A', A/, \ {j}.
'The condition {()) 2 ki, guarantees that C. in some sense, is a minimal blocking cluster. This is because if we remove a client violating this condition from the cluster C, then costavy (C) can never hecome >> 2 We will use this condition while analyzing the amortized recourse of our dynamic algorithm.
'If j is the first client being inserted, then there is no existing open facility. this case, we identify the facility i F which minimizes dag + fa, create critical cluster (i, (i3) and assign it to the level l E such that dij + fa E [2k-4, 26-3).
5

---

At this point, we fork into one of two cases. Case (a): If C' is an satellite cluster, then there is nothing further that needs be done, and we terminate the call to this subroutine. Case (b): If C (i. A) is a critical cluster, then let C" = (i, A²) denote the unique critical cluster with facility i just before the concerned call to the subroutine. Since there has to be exactly one critical cluster with facility i, we now convert the cluster C' = (i, A') into (possibly) multiple satellite clusters by performing the following operations for all clients j E A'.
. Create an satellite cluster (i, {j)) at level E((i, (()) E(C'), and set C + CU {(i, (1))
Finally, we remove the previous critical cluster C" from the current clustering, by setting C + C (C"), and then terminate the call to this subroutine.
The subroutine FiX-LEVEL(C); Suppose that the cluster C' = (1, A) is currently at level A: = ((C). We first deal with the corner case where C(i) {C} and A = 0. In this case, we simply set C \ {C}, and then terminate the call to this subroutine. Next, we check if C' is a critical cluster. If the answer is yes, then the cluster C' absorbs all the existing satellite clusters involving facility i at level k. To be more specific, for all satellite clusters (i. (j}) at level k2 we set A + A U {j} and C <-C C. \ {(i, (i))}. This ensures that Invariant 2 continues remain satisfied. Finally, at this point if it continues to be the case that costavg (C) 2 2 then we move the cluster C' up to level k + 1, by setting (CC) f E(C) + 1. We now terminate the call to this subroutine.
C <-C
2.4
Analysis of Our Dynamic Algorithm
The approximation guarantee of our dynamic algorithm follows from Theorem and Theorem 3. We defer the proof of Theorem 3 to Appendix A.
Theorem 3. The clustering C maintained by our dynamic algorithm always remains nice.
For the rest of this section, we focus on bounding the amortized recourse of our algorithm. Towards this end, whenever a client moves up (resp. down) one level, we say that the algorithm performs one unit of up-work (resp. down-work).
Lemma 1.
During any sequence of updates, the total recourse of the algorithm is at most plus O(1) times the total number of units of down-work that get performed.
First, note that the total facility-recourse is upper bounded, within a constant multiplicative factor, by the total client-recourse. This is because if we open new facility, then it necessarily implies that at least one client gets reassigned to the newly open facility.
Proof.
Next, observe that client gets assigned to a new facility i only if one of the following two events occurs. (1) The client j gets inserted during an update. (2) The client j participates in a blocking cluster C = (i, A) at level k (say), and the algorithm calls the subroutine Fix- (IX-BLOCKING(( C, k). The total recourse incurred due to events of type (1) is at most t. On the other hand, during an event of type (2) the concerned client j moves down from its current level {() to smaller level k. as per condition (b) in Definition 1. Thus, the total recourse incurred due to events of type (2) is at most the total units of down-work performed by the algorithm. The lemma follows.
It now remains to bound the total units of down- performed by our algorithm. We achieve this by means of token based argument, which in turn, requires us to first introduce the notion of an epoch of cluster, and then bound the total units of up-work performed by our algorithm during an epoch.
Epoch: Observe that when concerned cluster C = (i, A) first becomes part of the clustering C at some level (say) k we have costaey (C) < 2*-3 (see condition (a) in Definition 1). Subsequently, during its entire lifetime, the level of the cluster C can only increase (this can happen because of calls to the subroutine FIx- (C)). Accordingly, we partition the lifetime of the concerned cluster C (i. A) into multiple epochs, where an epoch refers to a maximal time-interval during which the level of the cluster does not increase. To be bit more specifie, suppose that the lifetime of cluster C' consists of epochs 1, 10,,,...,,, A). for some integer À 2 O. An epoch r E [0, A] begins when the cluster C- = (i, A) arrives at level is r, and ends when the cluster moves up from level k: r to level k + r + 1. Let A, denote the state of the set A just before the end of epoch r. The algorithm performs |Ar| units of up-work for the cluster C. (i, A) in epoch r. We will now upper bound the total units of up-work performed for the cluster C' during its entire lifetime, which is given by
Σd= |. The proof of Lemma 2 appears in Appendix C.

---

Lemma 2. Consider cluster C = (i, that first became part of the clustering C at level k. During its entire lifetime, our algorithm performs at most f1/2 units of up-work on this cluster C.
Tokens:
Recall that the opening costs of the facilities and the distances between the clients and facilities are all polynomially bounded by m = | Hence, there are at most Ollog m) levels the clustering C. To be more specific, there are two integral parameters T,, U E Z, with 0 I U - I. (log m.), such that {()) E [L, U] for all clients j E at all times. To analyse the amortised recourse of our algorithm, we now associate some tokens with each client in the following manner.
For each client j E D, there is token at each level l E [T. {())--
(1)
Observation holds since there are only O(log levels in the clustering C.
Observation 1. Whenever a client is inserted, it leads the creation of at most (log m) tokens. In contrast, whenever a client is deleted, it leads to the release of at most O(log m)) tokens. We assume that these released tokens get deposited into a special bank-account.
Observation 2. Whenever the algorithm performs one unit of down-work, it releases one token. We assume that 1/2 of this released token gets deposited into the special bank-account, and the remaining 1/2 of the token disappears after paying for the cost of the down-work being performed. In contrast, whenever the algorithm performs one unit of up-work, it withdraws one loken from the special bank-account to ensure that (1) continues to hold.
We assume that just before preprocessing, the special bank-account had zero balance. We will show that throughout the duration of our algorithm, the balance in this bank-account always remains non-negative. Towards this end, observe that the algorithm withdraws tokens from this account only when it performs up-work, and it performs up-work only when some cluster increases its level by one. Accordingly, we focus To (say). Suppose that C was assigned to level k (say) at time To- Let A denote the state of A at time Tu- As per condition (a) of Definition 1, at time Tu we have:
cluster C (i) that first becomes part of the clustering C at time
ft S costang (C) f: + E di
2
[A+]
|AT1|
fr/2k-3. The next observation holds since every client in A" had to move down least one level before the cluster C' is formed at level k, as per condition (b) of Definition 1. Observation 3. Just before a cluster C becomes part of the clustering C for the first time (say, at level k), the algorithu deposits at least f1/2k-1 many tokens into the special bank-accoun
Hence, we get |A7| 2
Lemma 2 implies that at most fa/ /2/2k-2 tokens get withdrawn from the bank-account because of the cluster C. By Observation 3, this is at most the number of tokens that get deposited into the same account just before the cluster C' is formed at time To. It follows that the bank-account never runs into negative balance. Theorem now follows from Observations 1, 2 and Lemma I.
Theorem 4. Starting from an empty set of clients, our algorithms spends at most (1 m)) total recourse to handle sequence of updates. So, the amortised recourse of our algorithm is Ollog m).
2.5 Implementation of our algorithm in Õ(m) amortized update time.
In Appendix we show how to implement our algorithm in amortized Ö(m) time per update. Here, we briefly describe how to quickly (i.e., in Ō(m) time) check whether Invariant 4 is satisfied.
For every facility and level k, let S(i, k) denote the sequence of clients that are at level larger than k, in increasing order of their distances from the facility i. The key observation is this: If there exists blocking cluster involving facility i at level k then there must exist a blocking cluster (with the same facility and at the same level) whose clients form a prefix of S 1)). This has the following implication. Suppose that we explicitly maintain these sequences {S(i, k)). Then given a specific pair (i, k), we can determine in only Õ(1) time (via a simple binary search and some standard data structures) whether or not there is blocking cluster involving facility i at level k. Finally, note that indeed maintain the sequences {S(i, })}} by paying factor ((m) overhead in update time. This is because whenever a client changes its level (or gets inserted / deleted) we need to modify at most mL = (m) of these sequences [S(i, }, where L is the number of levels.
In Appendix D, we present more fine tuned data structure, where we discretize the distances in powers of (1 + e). However, the main idea behind the data structure is the same as described above.
7

---

3 Experimental Evaluation
Datasets We experiment with three classic datasets" from UCI library Dua and Graff [2017]: KDD- Cup Stolfo et al. [2000] (311, 029 points of dimension 74) and song Bertin-Mahieux et al. [2011] (515, 345 points of dimension 90) Census Kohavi et al. [1996] (2, 458, 285 points of dimension 68). We did not alter in any way the dimensions of the data.
For each dataset, we only keep a 5, 000 points for each experiment as suffices to show the merits and limitations of the different approaches; also confirm that the relative behavior of the algorithms remains the same over the whole sequence of updates on one of the dataset that we consider. We consider the L2 distances of the embedding, and add 1/5000 to each distance to avoid having distances zero while not disturbing the structure of the instance.
Order of updates. We consider insertions and deletions of points under the sliding window model, where we order the points according to some permutation, and then we consider an interval (a.k.a., window) of l 1, 000 indices, which we slide from the beginning to the end of the ordered points and at each step form an instance containing the points that lie within the window limits; that is, as we slide the window, the new point that gets within the limits of the window treated as an insertion, while each point that falls outside the window limits is treated as a deletion.
Choice of facilities. We consider two different processes for choosing the set of facilities and their opening cost. The first way is to pick uniformly at random 5% of the point in the instance, remove them from the set of clients, and make them facilities. In the second variant we use 50% of the points as facilities. Using these two processes we generate six families of instances: Gensus-5%, Census-500 50% KDD-Cup-5% KDD-Cup-500 50%, song- -5,, and song-50%. These instances aim to cover the settings where the set of facilities is very restrictive or very broad, in order to assess the behavior of the algorithms in both of these settings.
We set the facility opening costs within a range to ensure that the problem does not become too easy; that is, we don't t want to the trivially good solutions of either opening only a single, or opening all facilities. We set the facility weights as follows: for given instance, we calculated the median distance of clients to their nearest facility, and multiplied this number by 100.
Algorithms We compare our algorithm against two main competing algorithms: 1) Following each point insertion or deletion, rerun from scratch the offline Greedy algorithm Jain et al. [2003], which we call GREEDYOFF and 2) The state of the art O (log(m)) approximation algorithm for the fully-dynamic facility location problem from Guo et al. [2020], which we call GKLX (from the authors last names). We also compare our algorithm to the baseline that simply maintains open the nearest facility of each of client. We call this baseline NEARESTFACILITY.
The behavior of our algorithm depends on two parameters: ju and e. The parameter e defines the base of the exponential bucketing scheme, and the parameter μı defines the level kij (see Invariant 3), so that (1++) -u-1 -M-1 < dij < (1 + (1+e)* In Section 2.2 we set e = 1 and 3 for ease of analysis. Both of these control parameters trade-off between running time, approximation, and recourse. While our theoretical part covers the case where 2 3 and = 1, we go beyond what is proven and explore setting values μ E {1,3) and e (0.05. 1). We use NICECLUSTERING(1
1. 0.05). NiCECLUSTERINGG(1 = c, 1), NICECLUSTERING(A = 3, e = 0.05), NICECLUSTERING(4 = 3, = 1) refer to the different configurations of our algorithm. We note that we did not try to optimize j and to minimize the approximation guarantee (the main goal was to get any constant) for simplicity of the presentation and the analysis, although we believe this is doable.
We defer the interested reader to Appendix D for implementation details.
Setup. All of our code is written in C++ and is available online 6. We used a e2-standard- 16 Google Cloud instance, with 16 cores, 2.20GHz Intel(R) Xeon(R) processor, and 64 GiB main memory.
'None of these datasets is ideal for our setting they lack information that determines the order of insertions and deletions. However, datasets and setup are typical in studies of dynamic algorithms (see, e.g.. Cohen- et al. [2019]). 'https://githur com/ gowg/ggooleeeooooooo moogle-researeeee ch/ google- meooglerreearree ch/ http//tee/mmaee srree/master/fullyy _dyamiic__ facility_location
not aware of any targeted datasets that openly available. We note that
8

---

3.1 Results
Throughout this section, as the relative behavior of the algorithms is similar among the different datasets, we use the KDD-Cup-599 and KDD-Cup-50% datasets to amalyze the performance of the algorithm, and summarize the behavior of the algorithms for the rest of the datasets (we defer the detailed description and the plots of the remaining datasets to Appendix E).
Given that our process of creating the instances contain randomized decisions, we repeat each of our experiments 10 times and report the mean relative behavior of the algorithms in Appendix For visualization purposes, we discuss the outcome of a single experiment; repeating the experiment multiple times does not alter significantly the relative behavior of the algorithms.
Moreover, assessed the performance of NiCECLUSTERING( identically to NICECLUSTERING( = 3, c = 0.05) in terms of solution cost and time, but exhibits slightly larger recourse. Hence, omit it avoid complicating the plots and tables. Finally, only run GREEDYOFF OFF on the datasets IDD-Cup-559 4up-5% and MODD-Cp--50% and only once, for illustration purposes as it is very computationally expensive run.
1, 0.05), it performs
Solution cost. We analyze the different algorithms in terms of the cost of their solution. Figure summarizes the results for both settings where we consider 5% and 50% of the points to be facilities.
Total cost, KDD-Cup-5%
Total cost, KDD-Cup-50%
423
3033
2003
Nccooffie NosGkolorquue 1m1.2 "Neod Meesuusehee 2 002 Bei Gassgy
Figure 2: The solution cost by the different algorithms over the whole sequence of updates, on KDD-Cup-5% and KDD-Cup-50%.
As expected, the smaller the values of μ and e in NICECLUSTERING, the better the solution quality. NICECLUSTERING(U = 3, = 0.05) perform almost identically to GREEDYOFF, which is an algorithm that is very computationally expensive. Over 10 repetitions, NICECLUSTERING (u 3. = 0.05) performs roughly 17% 29% better and 55% 67% better than GKLX on KDD-Cup 5% and KDD-Cup-50% respectively. The > 35% happens because in this particular dataset there few facilities with small distances to many clients, GKLX prioritizes minimizing opening costs rather than connection cost in this case. On the other datasets NiCECLUSTERING(/ = 3, = 0.05) outperforms GKLX by 14% 30% (see Appendix F).
Recourse. Next, we study the recourse occurred by each of the algorithms that we consider on the datasets KDD-Cup-5% and XDD-Cup-50%. Figure 3 summarizes the results of this experiment.
Recourse, KDD-Cup-5% (log scale)
Recourse, KDD Cup-ccp-50% (log scale)
53
2000
Kiicke DXLX - Cewnioo
1iesSusserssee 000
Figure 3: The cumulative recourse incurred by the algorithms that we consider over the whole sequence of updates, on KDD-Cup-5% (left), and KDD-Cup-50% (right). Missing lines imply 0 recourse throughout. The plot is in log scale.
While all algorithms, except GREEDY have limited recourse (considering the window size is 1, 000 and the length of the update sequence is 9, 500 and 5, 000 for KDD-Cup-5% and KDD-

---

3, = Cup-50%. respectively), GKLX performs the best (NEARESTFACILITY trivially has no recourse). Naturally, smaller values of μ and in our algorithm make perform closer to GREEDYOFF (which has no recourse guarantees) in terms of cost, implying higher recourse. While GKLX performs better than NICECI.USTERING on KDD-Cup-5% they are comparable on KDD-Cup-50%, Repeating the experiment 10 times show similar relative behavior.
Running time. As expected, our algorithm is slower compared to GKLX. NICECLUSTERINGİ4 = 3. = NICECI.USTERIGG((: = e = 1) are one order of magnitude slower. This dues to the fact that GKLXX, apart from the initial preprocessing phase and determining the nearest facility to each client, spends only polylogarithmic time per update as operates on tree structure of logarithmic depth. In fact, after the preprocessing phase, GKLX does not need to store the connections between clients and facilities; it suffices to remember the nearest facility to each client. The reduced space allows better cashing and fewer main memory accesses. On the other hand, our algorithm stores explicitly the connection costs of clients and visit them regularly. NICECLUSTERINGI 0.05) is slower by another order of magnitude, due to the increased number of level in our algorithm. We refer to Appendix E. for the running time plots. Finally, GREEDYOFF is over two orders of magnitude slower compared to the slowest of the variants of our algorithm.
Total Cost. FUlI KDD Cup
Recourse, KDD Cup (lag scale)
30333
20233
123
23
12333
-3
130000
220000
200333
4X00CE
5C2300
2000CC
100000 203030
200233
100002
SC4920
000KE:
The solution cost by NICECLUSTERINGÍA GKLX over the whole update sequence, on Full-KDD- Cup (left), and the total recourse incurred by these algorithms,, in log scale, Full-KDD-Cup Cup (right). Missing lines imply recourse throughout.
Figure 4:
3, -3 1), NICECLUSTERING(( c, 1).
Consistency over the long sequence of updates To showcase that the relative behavior of the algorithms is not affected by our choice to restrict each datasets to the first 5000 points, we run the algorithm on whole KDD-Cup dataset consisting of 31 1,029 points, where we choose 250 points as facilities (the same absolute number as in the case of KDD-Cup-5%) Similarly to the rest of the experiments, we consider insertions and deletions of points under the sliding window model (with = 1000). We refer to this instance as Full-KDD-GU that is NICECLUSTERING, the total cost, and recourse; the results are shown in Figure 4. The conclusions from the previous experiments on the restricted dataset hold also in this experiment. However, First, the performance of GKLX fluctuates more compared to NICECLUSTERINGG/ = 3, = 1) and NICECLUSTERING((U
We compare the most competitive algorithms, 3, 1). NICECLUSTERING(A = 1, 1). and GKLX in terms of
observe two behaviors.
1, 1). This can be attributed to the fact that the algorithm doesn't 't adapt rapidly to the changes in the instance. To a lesser extend, the behavior of NICECLUSTERING(A 3, ===1 1) also fluctuates more than NICECL.STEERINGG second observation is that while NICECI.USTERINGG/A = 3, = 1) and GKLX incur very little recourse, while NICECLUSTERINGI/ observations are related. This implies that NICECLUSTERINGI = L, = 1) adapts more rapidly to the changing dataset so that it able to maintain better solution.
1, = 1). for the same reasons. The
L, 1) continuously incurs (limited) recourse. These two
Conclusion of Experiments. We showed that our algorithm outperforms, often significantly, in terms of solution cost the GKIX algorithm, but in some cases exhibits an increase in recourse (while still being a small absolute number) and it is also slower. We believe the our algorithm is a good fit for applications where solution quality is very important, and one wants to maintain stable solution in reasonable time. Given that our algorithm performs almost in par with GREEDYOFT, becomes a good choice in cost-sensitive applications on dynamic data.
Acknowledgments and Disclosure of Funding
Sayan Bhattacharya is supported by Engineering and Physical Sciences Research Council, UK (EPSRC) Grant EP/S03353X/I.
10

---

References
Thierry Bertin-Mahieux, Daniel PW Ellis, Brian Whitman, and Paul Lamere. The million song dataset. 2011.
TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, pages 579-587, 2018.
Vincent Codan-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpie, and Chris Schwiegelshohn. Fully dynamic consistent facility location. Advances in Neural Information Processing Systems, 32, 2019.
Marek Cygan, Artur Czumaj. Marcin Mucha, and Piotr Sankowski. Online facility location with delctions. In Proceedings 26th Annual European Symposium on Algorithms, page 21:1-21:15, 2018.
Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, and Christian Sohler. (I+ e)-
approximation for facility location in data streams, In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1710-1728. SIAM, 2013.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://arcchive.css uci edu/ml.
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent clustering for general metrics. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2660-2678. SIAM, 2021.
Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008.
Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A tree structure for dynamic facility location. In Proceedings 26th Annual European Symposium on Algorithms, page 39:1-39:13, 2018.
Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. Fully dynamic k-center clustering in low dimensional metrics. In 202/ Proceedings of the Workshop Algorithm Engineering and Experiments (ALENEX), pages 143-153. SIAM, 2021.
Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of algorithms, 31(1):228-244 1999.
Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. the facility location problem in online and dynamic models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl--cibniz ZZntrrum für Informatik, 2020.
Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. Consistent k-median: Simpler, better and robust. In International Conference on Artificial Intelligence and Statistics, pages 1135-1144 1143. PMLR, 2021.
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 537-550, 2017.
Monika Henzinger, Dariusz. Leniowski, and Claire Mathieu. Dynamic clustering to minimize the sum of radii. Algorithmica, 82(11))3183-3194 2020.
Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In Proceedings of the sixth annual ACM Symposium on Theory of Computing, pages 373-380, 2004.
Mohammad Reza Karimi Jaghargh, Andreas Krause, Silvio Lattanzi, and Sergei Vassilvtiskii. Con- sistent online optimization: Convex and submodular. The 22nd International Conference on Artificial Intelligence and Statistics, pages 2241-2250 PMLR. 2019.

---

Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. Journal of the ACM (JACM), 5006) 2003.
Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: A decision- tree hybrid. In Kdd, volume 96, pages 202-207, 1996.
Bernhard Korte and Jens Vygen. Facility Location, pages 629-665, Springer Berlin Heidelberg, Berlin, Heidelberg, 2018.
Christiane Lammersen and Christian Sohler. Facility location in dynamic geometric data streams, In European Symposium on Algorithms, pages 660-671. Springer, 2008
Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In International Conference on Machine Learning, pages 1975-1984. PMLR, 2017.
Silvio Lattanzi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakub M Tarnawski, and Morteza Zadi- moghaddam. Fully dynamic algorithm for constrained submodular optimization. Advances in Neural Information Processing Systems, 33: 129333 2020.
Shi Li. A 1. 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45 58, 2013. ISSN 0890-5401. doi: https:/doi.orr// 101 1..6//..c.2012..000 007. 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).
Adam Meyerson. Online facility location. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 426-431. IEEE, 2001.
S.J. Stolfo, Wei Fan, Wenke Lee, A. Prodromidis, and P.K. Chan. Cost-based modeling for fraud and intrusion detection: results from the jam project. Proceedings DARPA Information Survivability Conference and Exposition. DISCEX 00, volume 2, pages 130-144 vol.2, 2000. doi: 10. 10.1109/ DISCEX.2000.821515
Paper checklist
Q (a):Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
A: Yes. We prove the claims for theoretical guarantee, and conduct the appropriate experiments to support our claims on performance.
Q (b): Have you read the ethics review guidelines and ensured that your paper conforms to them?
A: Yes.
(c): Did you discuss any potential negative societal impacts of your work?
A: No. This paper studies basic algorithmic question. We are not aware of direct applications of the facility location problem with negative socictal impact. Our findings and code are made openly available for all.
Q (d): Did you describe the limitations of your work?
A: Yes. In the experimental section discuss both strengths and weaknesses of our algorithm.
On theoretical results
(a): Did you state the full set of assumptions of all theoretical results?
A: yes.
Q (b): Did you include complete proofs of all theoretical results?
A: yes.
12

---

On experiments
(a): Did you include the code, data, and instructions needed reproduce the main experimental results (either in the supplemental material or as a URL)?
A: No. We will the code is made available.
Q (b): Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
A: There is no training in this paper.
Q (c): Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?
A: Yes, we repeated the experiments 10 times, and report the mean and standard deviation in the Appendix F.
Q (d): Did you include the amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?
A: Yes. The experimental section reports the type of machine that used.
On using existing assets.
(a): If your work uses existing assets, did you cite the creators?
A: Yes. We cited the datasets that we used.
Q (b): Did you mention the license of the assets?
A: No. These datasets have no individual licences in the UCI repository.
Q (c): Did you include any new assets either the supplemental material or as URL?
A: No. We released the code.
Q (d): Did you discuss whether and how consent obtained from people whose data you 're using/curating?
A: Yes. They the data are available at the UCI machine learning repository, and no additional licence reported.
Q (e): Did you discuss whether the data you are using/curating contains personally identifiable information offensive content?
A: No. This is clear since the data are simply embeddings.
13


Reviews:
[{"review_id": "zdZLSoVJFmW", "reviewer": "Reviewer_f1Wt", "summary": "Dynamic Facility Location problem (with client insertions and deletions) is being considered in which modifying the solution involves additional cost (recourse). The authors provide an algorithm that maintains a constant factor approximation solution to the current instance\nwith the additional guaranty that the amortized recourse is polylogarithmic in the instance size.\n\nTechnically, the result is obtained by an adaptation of the greedy JMS algorithm for the static case. The solution maintained by the algorithm is formally proved to be close to what the greedy algorithm would produce for the current instance, which suffice to argue for it being a constant factor approximate solution.", "questions": "Minor comments:\n- line 26 \"been extensively\" -> \"been studied extensively\"\n- l. 26 \"for for\"\n- l. 209 \"repeated checks\" -> perhaps \"repeatedly checks\"?\n- l. 254 and l. 256 \"total units of ...\" -> either \" total ...\" or \"total number of units of ...\"", "limitations": "The experimental part dresses some practical limitations adequately. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* it is one of the central optimization problems (not a very special case of it)\n* the provided solution is elegant\n* the obtained result appears to be relevant\n\nWeaknesses:\n* I find the notion of \"ordinary clusters\" somewhat annoying, these are just \"one client connected to one facility\" in the end.\n  It appears to be there just to enable using term \"clusters\" for both the real clusters called \"critical clusters\" in the paper, and these client-facility pairs called \"ordinary clusters\" in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nCJLAFQmaY", "reviewer": "Reviewer_d29J", "summary": "The authors develop the first fully dynamic algorithm for facility location with constant approximation guarantee and polylogarithmic recourse per update. This guarantees that the current solution does not change ``too much'' after any update. Prior to this this work, the best known fully dynamic algorithm achieved a logarithmic approximation guarantee and polylog update time. Their theoretical results are complemented with an experimental evaluation on real-world data.", "questions": "The authors answered convincingly my question about the polylog amortized running time. ", "limitations": "I could not find any potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ the first constant approximation algorithm for facility location with polylog recourse per update\n+ facility location is relevant to the machine learning community (it can be seen as the Lagrangian relaxation of k-median), while there have been increasing efforts in recent years to develop fully dynamic algorithms that are stable\n+ the theoretical results are non-trivial and interesting\n+ the paper is well written and relatively easy to follow\n\n- the constant approximation ratio is relatively large (2^10, as far as I understood)\n- I could not find an analysis of the amortized running time. Is the amortized running time per update polylog? Update: the authors pointed our convincingly that their approach is almost optimal. \n- the experimental evaluation could be improved. The authors considered only the first 5000 points for each dataset, claiming that there should not be much difference when processing the whole dataset. It is not clear whether this is the case. \n- the experimental evaluation only considers the sliding window model. It would be more interesting to consider also updates that do not fit in the sliding window model, as they can be handled by the algorithm. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UgzXLgZomCX", "reviewer": "Reviewer_6GBX", "summary": "The paper considers the facility location problem in the fully dynamic setting, where clients can come and go. The goal is to maintain a near-optimal solution and simultaneously minimize the recourse, namely the number of facility openings/closings $+$ reassignments of clients to centers. There is a caveat: the algorithm in this paper only works when the ratio of maximum distance / opening cost to minimum distance / opening cost is bounded polynomially in the number of candidate facility locations $m$. In this setting, the paper gives a dynamic algorithm that maintains a constant approximation guarantee, and uses $O(\\log m)$ amortized recourse per change. The main idea is to relax the greedy algorithm which picks repeatedly a cluster (facility $+$ connected clients) of minimum average cost, then show how to maintain such a solution dynamically with small recourse. There are some experimental results which I don't know how to evaluate.", "questions": "Are there any lower bounds on the achievable recourse?", "limitations": "Irrelevant.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The dynamic setting is well-motivated and the solution is quite interesting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M8tqGLo9cWm", "reviewer": "Reviewer_GbJJ", "summary": "The paper studies fully dynamic facility location for general metric spaces, where update operations are allowed to insert or delete clients. The main result is a dynamic algorithm which maintains a O(1)-approximate solution using O(log m) amortized recourse. Here, m is the number of facilities and the recourse is the number of clients and facilities that are reassigned after each update. The update time of the algorithm is O(m polylog(m)).\n\nThe approximation ratio improves upon a paper by Guo et al. (APPROX/RANDOM'20) which maintained a O(log m)-approximate solution with recourse and update time O(log m). The recourse of the new and the old result is the same, but the Guo et al. paper achieves a faster guaranteed update time.\n\nThe bound on the approximation ratio is obtained by defining a set of invariants and showing that when the invariants are satisfied, the maintained solution is \"close\" to the solution of an offline greedy algorithm which obtains a O(1)-approximation. It is then shown how these invariants can be maintained dynamically. The recourse bound is obtained using a technique introduced by Gupta et al. (STOC'17).", "questions": "My main question is how it is checked whether Invariant 4 is satisfied or not. This is not explained in the main text and I was not sure how to do this this efficiently. I looked at the corresponding section in the supplementary material, which provides a routine for finding blocking clusters. However, it is not immediately clear to me why this routine captures *all* possible blocking clusters (if there exists one). A proof for this might be interesting.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(S1) Facility location is a fundamental problem and dynamic variants of it are highly interesting.\n\n(S2) The theoretical results are interesting and non-trivial to obtain.\n\n\nWeaknesses:\n\n(W1) The main weakness of the theoretical result is certainly that only a bound on the recourse is obtained, while the bounds on space usage and update time are not very impressive. More concretely, in the streaming community one typically wishes for sublinear space usage and in the dynamic community one aims for sublinear update times; neither of this is achieved here.\n\n*Update:* In the rebuttal, the authors pointed out that since a general metric space is considered, even specifying a single client insertion takes time $\\Omega(m)$. Hence, an update time of $\\tilde{O}(m)$ is somewhat inevitable. I still believe that this is property of the model is somewhat undesirable from a dynamic algorithms point of view, but I will not hold it against the paper.\n\n(W2) The experimental evaluation is missing details and does not fully allow me to judge the quality of the results. For example, in Figure 3 (left), the line for GKLX is missing even though in the text (Lines 367--373) it is talked about it. It also seems like the proposed method only achieves factor 2.5 better approximation ratios than GKLX, while requiring much more recourse and update times. This certainly makes the result less interesting.\n\n(W3) The submission contains quite a lot of typos.\n\n\nMinor comments:\n- Line 26: The word \"studied\" is missing.\n- Line 26: \"for for\"\n- Throughout the paper, the citation style is slightly confusing because it just lists author names but they are not used in the text (e.g., Line 47).\n- Line 103: |C| is not defined, I presume it refers to |A|?\n- I found the definition of ordinary and critical clusters a bit confusing and only understood it after I kept on reading.\n- Lines 129--135: This part was hard to understand because nice clustering were not introduced yet.\n- Line 136: Point out that C is not necessarily from \\mathcal{C} but could be any possible cluster.\n- Line 159: I find this reference to the relaxed greedy algorithm a bit confusing because this algorithm has not been formally defined.\n- I find the size of the instances in the experiments a bit small. Having only 1000 points seems a bit unrealistic.\n- Experiments: I would appreciate a clearer discussion about the tradeoff between better approximation and larger running times.\n- Experiments: Since the algorithm works for general metric spaces, why were only L_2-distances considered?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept