Efficient and Stable Fully Dynamic Facility Location
Authors: Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Collaboration | Sayan Bhattacharya Department of Computer Science University of Warwick Coventry, CV47AL, United Kingdom s.bhattacharya@warwick.ac.uk Silvio Lattanzi Google Research silviol@google.com Nikos Parotsidis Google Research nikosp@google.com |
| Pseudocode | Yes | Figure 1: FIX-CLUSTERING(.). (Contains numbered steps of an algorithm) |
| Open Source Code | Yes | All of our code is written in C++ and is available online 6. https://github.com/google-research/google-research/tree/master/fully_dynamic_facility_location |
| Open Datasets | Yes | We experiment with three classic datasets 5 from UCI library Dua and Graff [2017]: KDDCup 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). |
| Dataset Splits | No | There is no training in this paper. The paper uses a sliding window model for data updates rather than traditional train/validation/test splits for model training. |
| Hardware Specification | Yes | We used a e2-standard-16 Google Cloud instance, with 16 cores, 2.20GHz Intel(R) Xeon(R) processor, and 64 Gi B main memory. |
| Software Dependencies | No | All of our code is written in C++. Specific version numbers for libraries or dependencies are not provided. |
| Experiment Setup | Yes | The behavior of our algorithm depends on two parameters: µ and ϵ. The parameter ϵ defines the base of the exponential bucketing scheme, and the parameter µ defines the level κ ij (see Invariant 3), so that (1+ϵ)κ ij µ 1 dij < (1+ϵ)κ ij µ. In Section 2.2 we set ϵ = 1 and µ = 3 for ease of analysis. ...explore setting values µ {1, 3} and ϵ {0.05, 1}. |