Dynamic Facility Location in High Dimensional Euclidean Spaces

Sayan Bhattacharya, Gramoz Goranci, Shaofeng H.-C. Jiang, Yi Qian, Yubo Zhang
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:3763-3775, 2024.

Abstract

We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces Rd. For any c≥1, our algorithm achieves O(c)-approximation, supports point updates in ˜O(poly(d)n1/c+o(1)) amortized time and incurs O(1) amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-bhattacharya24a, title = {Dynamic Facility Location in High Dimensional {E}uclidean Spaces}, author = {Bhattacharya, Sayan and Goranci, Gramoz and Jiang, Shaofeng H.-C. and Qian, Yi and Zhang, Yubo}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {3763--3775}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/bhattacharya24a/bhattacharya24a.pdf}, url = {https://proceedings.mlr.press/v235/bhattacharya24a.html}, abstract = {We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces $\mathbb{R}^{d}$. For any $c \geq 1$, our algorithm achieves $O(c)$-approximation, supports point updates in $\tilde{O}(\mathrm{poly}(d)n^{1/c + o(1)})$ amortized time and incurs $O(1)$ amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.} }
Endnote
%0 Conference Paper %T Dynamic Facility Location in High Dimensional Euclidean Spaces %A Sayan Bhattacharya %A Gramoz Goranci %A Shaofeng H.-C. Jiang %A Yi Qian %A Yubo Zhang %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-bhattacharya24a %I PMLR %P 3763--3775 %U https://proceedings.mlr.press/v235/bhattacharya24a.html %V 235 %X We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces $\mathbb{R}^{d}$. For any $c \geq 1$, our algorithm achieves $O(c)$-approximation, supports point updates in $\tilde{O}(\mathrm{poly}(d)n^{1/c + o(1)})$ amortized time and incurs $O(1)$ amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.
APA
Bhattacharya, S., Goranci, G., Jiang, S.H., Qian, Y. & Zhang, Y.. (2024). Dynamic Facility Location in High Dimensional Euclidean Spaces. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:3763-3775 Available from https://proceedings.mlr.press/v235/bhattacharya24a.html.

Related Material