Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: The dynamic setting is well-motivated and the solution is quite interesting.
questions: Are there any lower bounds on the achievable recourse?
limitations: Irrelevant.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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
with the additional guaranty that the amortized recourse is polylogarithmic in the instance size.

Technically, 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.
strengths_and_weaknesses: Strengths:
* it is one of the central optimization problems (not a very special case of it)
* the provided solution is elegant
* the obtained result appears to be relevant

Weaknesses:
* I find the notion of "ordinary clusters" somewhat annoying, these are just "one client connected to one facility" in the end.
  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.
questions: Minor comments:
- line 26 "been extensively" -> "been studied extensively"
- l. 26 "for for"
- l. 209 "repeated checks" -> perhaps "repeatedly checks"?
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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)).

The 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.

The 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).
strengths_and_weaknesses: Strengths:

(S1) Facility location is a fundamental problem and dynamic variants of it are highly interesting.

(S2) The theoretical results are interesting and non-trivial to obtain.


Weaknesses:

(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.

*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.

(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.

(W3) The submission contains quite a lot of typos.


Minor comments:
- Line 26: The word "studied" is missing.
- Line 26: "for for"
- 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).
- Line 103: |C| is not defined, I presume it refers to |A|?
- I found the definition of ordinary and critical clusters a bit confusing and only understood it after I kept on reading.
- Lines 129--135: This part was hard to understand because nice clustering were not introduced yet.
- Line 136: Point out that C is not necessarily from \mathcal{C} but could be any possible cluster.
- Line 159: I find this reference to the relaxed greedy algorithm a bit confusing because this algorithm has not been formally defined.
- I find the size of the instances in the experiments a bit small. Having only 1000 points seems a bit unrealistic.
- Experiments: I would appreciate a clearer discussion about the tradeoff between better approximation and larger running times.
- Experiments: Since the algorithm works for general metric spaces, why were only L_2-distances considered?
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: + the first constant approximation algorithm for facility location with polylog recourse per update
+ 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
+ the theoretical results are non-trivial and interesting
+ the paper is well written and relatively easy to follow

- the constant approximation ratio is relatively large (2^10, as far as I understood)
- 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. 
- 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. 
- 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. 


questions: The authors answered convincingly my question about the polylog amortized running time. 
limitations: I could not find any potential negative societal impact.
review_title: null

Meta-review: metareview: The paper considers facility location problem in a well-motivated fully-dynamic setting where clients can arrive and depart. The goal is to maintain a near-optimal solution and simultaneously minimize the amount of "recourse" (the number of facility openings/closings and reassignments of clients to centers). However, this algorithm only works when the ratio of maximum distance / opening cost to minimum distance / opening cost is bounded polynomially in the number m of given facility locations; the paper presents an algorithm that maintains a constant-factor approximation guarantee while using an O(log m)--amount of amortized recourse per change. The idea is to relax the classical greedy algorithm of Jain-Mahdian-Saberi for the static case.which picks repeatedly a cluster---a facility along with the clients assigned to it---of minimum average cost, and to show how to maintain such a solution dynamically with small recourse. 

The paper was generally strongly appreciated by the reviewers. 
confidence: Certain
Decision: Accept