Timezone: »
Poster
Fully Dynamic Consistent Facility Location
Vincent Cohen-Addad · Niklas Oskar D Hjuler · Nikos Parotsidis · David Saulpic · Chris Schwiegelshohn
Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #32
We consider classic clustering problems in fully dynamic data streams, where data elements can be both inserted and deleted. In this context, several parameters are of importance: (1) the quality of the solution after each insertion or deletion, (2) the time it takes to update the solution, and (3) how different consecutive solutions are. The question of obtaining efficient algorithms in this context for facility location, $k$-median and $k$-means has been raised in a recent paper by Hubert-Chan et al. [WWW'18] and also appears as a natural follow-up on the online model with recourse studied by Lattanzi and Vassilvitskii [ICML'17] (i.e.: in insertion-only streams).
In this paper, we focus on general metric spaces and mainly on the facility location problem. We give an arguably simple algorithm that maintains a constant factor approximation, with $O(n\log n)$ update time, and total recourse $O(n)$. This improves over the naive algorithm which consists in recomputing a solution at each time step and that can take up to $O(n^2)$ update time, and $O(n^2)$ total recourse. These bounds are nearly optimal: in general metric space, inserting a point take $O(n)$ times to describe the distances to other points, and we give a simple lower bound of $O(n)$ for the recourse. Moreover, we generalize this result for the $k$-medians and $k$-means problems: our algorithm maintains a constant factor approximation in time $\widetilde{O}(n+k^2)$.
We complement our analysis with experiments showing that the cost of the solution maintained by our algorithm at any time $t$ is very close to the cost of a solution obtained by quickly recomputing a solution from scratch at time $t$ while having a much better running time.
Author Information
Vincent Cohen-Addad (CNRS & Sorbonne Université)
Niklas Oskar D Hjuler (University of Copenhagen)
Nikos Parotsidis (University of Copenhagen)
David Saulpic (Ecole normale supérieure)
Chris Schwiegelshohn (Sapienza, University of Rome)
More from the Same Authors
-
2021 Spotlight: Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces »
Vincent Cohen-Addad · David Saulpic · Chris Schwiegelshohn -
2022 : Scalable and Improved Algorithms for Individually Fair Clustering »
Mohammadhossein Bateni · Vincent Cohen-Addad · Alessandro Epasto · Silvio Lattanzi -
2023 Poster: Multi-Swap k-Means++ »
Lorenzo Beretta · Vincent Cohen-Addad · Silvio Lattanzi · Nikos Parotsidis -
2023 Poster: Private estimation algorithms for stochastic block models and mixture models »
Hongjie Chen · Vincent Cohen-Addad · Tommaso d'Orsi · Alessandro Epasto · Jacob Imola · David Steurer · Stefan Tiegel -
2022 Poster: Improved Coresets for Euclidean $k$-Means »
Vincent Cohen-Addad · Kasper Green Larsen · David Saulpic · Chris Schwiegelshohn · Omar Ali Sheikh-Omar -
2022 Poster: Near-Optimal Correlation Clustering with Privacy »
Vincent Cohen-Addad · Chenglin Fan · Silvio Lattanzi · Slobodan Mitrovic · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2022 Poster: Near-Optimal Private and Scalable $k$-Clustering »
Vincent Cohen-Addad · Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2021 Poster: Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces »
Vincent Cohen-Addad · David Saulpic · Chris Schwiegelshohn -
2021 Poster: Parallel and Efficient Hierarchical k-Median Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Poster: Fast and Accurate $k$-means++ via Rejection Sampling »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Poster: On the Power of Louvain in the Stochastic Block Model »
Vincent Cohen-Addad · Adrian Kosowski · Frederik Mallmann-Trenn · David Saulpic -
2019 Poster: Subquadratic High-Dimensional Hierarchical Clustering »
Amir Abboud · Vincent Cohen-Addad · Hussein Houdrouge -
2018 Poster: Online Reciprocal Recommendation with Theoretical Performance Guarantees »
Claudio Gentile · Nikos Parotsidis · Fabio Vitale -
2018 Poster: Clustering Redemption–Beyond the Impossibility of Kleinberg’s Axioms »
Vincent Cohen-Addad · Varun Kanade · Frederik Mallmann-Trenn -
2018 Poster: On Coresets for Logistic Regression »
Alexander Munteanu · Chris Schwiegelshohn · Christian Sohler · David Woodruff -
2018 Spotlight: On Coresets for Logistic Regression »
Alexander Munteanu · Chris Schwiegelshohn · Christian Sohler · David Woodruff -
2017 Poster: Balancing information exposure in social networks »
Kiran Garimella · Aristides Gionis · Nikos Parotsidis · Nikolaj Tatti -
2017 Poster: Hierarchical Clustering Beyond the Worst-Case »
Vincent Cohen-Addad · Varun Kanade · Frederik Mallmann-Trenn