Timezone: »
The study of online algorithms and competitive analysis provides a solid foundation for studying the quality of irrevocable decision making when the data arrives in an online manner. While in some scenarios the decisions are indeed irrevocable, there are many practical situations when changing a previous decision is not impossible, but simply expensive. In this work we formalize this notion and introduce the consistent k-clustering problem. With points arriving online, the goal is to maintain a constant approximate solution, while minimizing the number of reclusterings necessary. We prove a lower bound, showing that \Omega(k \log n) changes are necessary in the worst case for a wide range of objective functions. On the positive side, we give an algorithm that needs only O(k^2 \log^4n) changes to maintain a constant competitive solution, an exponential improvement on the naive solution of reclustering at every time step. Finally, we show experimentally that our approach performs much better than the theoretical bound, with the number of changes growing approximately as O(\log n).
Author Information
Silvio Lattanzi (Google)
Sergei Vassilvitskii (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: Consistent k-Clustering »
Tue. Aug 8th 12:48 -- 01:06 AM Room C4.6 & C4.7
More from the Same Authors
-
2023 Poster: Speeding Up Bellman Ford via Minimum Violation Permutations »
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii -
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2023 Tutorial: How to DP-fy ML: A Practical Tutorial to Machine Learning with Differential Privacy »
Sergei Vassilvitskii · Natalia Ponomareva · Zheng Xu -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Spotlight: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2021 Poster: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2021 Oral: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2019 Poster: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Poster: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2019 Oral: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Oral: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2019 Poster: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii -
2019 Poster: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2019 Poster: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii -
2019 Oral: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2018 Poster: Competitive Caching with Machine Learned Advice »
Thodoris Lykouris · Sergei Vassilvitskii -
2018 Oral: Competitive Caching with Machine Learned Advice »
Thodoris Lykouris · Sergei Vassilvitskii -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni