Timezone: »
Poster
Online Facility Location with Multiple Advice
Matteo Almanza · Flavio Chierichetti · Silvio Lattanzi · Alessandro Panconesi · Giuseppe Re
Clustering is a central topic in unsupervised learning and its online formulation has received a lot of attention in recent years. In this paper, we study the classic facility location problem in the presence of multiple machine-learned advice. We design an algorithm with provable performance guarantees such that, if the advice is good, it outperforms the best-known online algorithms for the problem, and if it is bad it still matches their performance.We complement our theoretical analysis with an in-depth study of the performance of our algorithm, showing its effectiveness on synthetic and real-world data sets.
Author Information
Matteo Almanza (Sapienza University of Rome)
Flavio Chierichetti (Sapienza University)
Silvio Lattanzi (Google Research)
Alessandro Panconesi (Sapienza, University of Rome)
Giuseppe Re (Sapienza University of Rome)
More from the Same Authors
-
2022 : Scalable and Improved Algorithms for Individually Fair Clustering »
Mohammadhossein Bateni · Vincent Cohen-Addad · Alessandro Epasto · Silvio Lattanzi -
2022 Poster: Active Learning of Classifiers with Label and Seed Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice · Maximilian Thiessen -
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: Efficient and Stable Fully Dynamic Facility Location »
Sayan Bhattacharya · Silvio Lattanzi · Nikos Parotsidis -
2021 Poster: Robust Online Correlation Clustering »
Silvio Lattanzi · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang · Rudy Zhou -
2021 Poster: Parallel and Efficient Hierarchical k-Median Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2021 Poster: Efficient and Local Parallel Random Walks »
Michael Kapralov · Silvio Lattanzi · Navid Nouri · Jakab Tardos -
2021 Poster: On Margin-Based Cluster Recovery with Oracle Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Poster: Fully Dynamic Algorithm for Constrained Submodular Optimization »
Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Jakub Tarnawski · Morteza Zadimoghaddam -
2020 Oral: Fully Dynamic Algorithm for Constrained Submodular Optimization »
Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Jakub Tarnawski · Morteza Zadimoghaddam -
2020 Poster: Sliding Window Algorithms for k-Clustering Problems »
Michele Borassi · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam -
2020 Poster: Fast and Accurate $k$-means++ via Rejection Sampling »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Poster: Online MAP Inference of Determinantal Point Processes »
Aditya Bhaskara · Amin Karbasi · Silvio Lattanzi · Morteza Zadimoghaddam -
2020 Poster: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Oral: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Session: Orals & Spotlights Track 05: Clustering/Ranking »
Silvio Lattanzi · Katerina Fragkiadaki -
2019 : Coffee Break & Poster Session 1 »
Yan Zhang · Jonathon Hare · Adam Prugel-Bennett · Po Leung · Patrick Flaherty · Pitchaya Wiratchotisatian · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam · Theja Tulabandhula · Fabian Fuchs · Adam Kosiorek · Ingmar Posner · William Hang · Anna Goldie · Sujith Ravi · Azalia Mirhoseini · Yuwen Xiong · Mengye Ren · Renjie Liao · Raquel Urtasun · Haici Zhang · Michele Borassi · Shengda Luo · Andrew Trapp · Geoffroy Dubourg-Felonneau · Yasmeen Kussad · Christopher Bender · Manzil Zaheer · Junier Oliva · Michał Stypułkowski · Maciej Zieba · Austin Dill · Chun-Liang Li · Songwei Ge · Eunsu Kang · Oiwi Parker Jones · Kelvin Ka Wing Wong · Joshua Payne · Yang Li · Azade Nazi · Erkut Erdem · Aykut Erdem · Kevin O'Connor · Juan J Garcia · Maciej Zamorski · Jan Chorowski · Deeksha Sinha · Harry Clifford · John W Cassidy -
2018 Poster: A Reduction for Efficient LDA Topic Reconstruction »
Matteo Almanza · Flavio Chierichetti · Alessandro Panconesi · Andrea Vattani -
2018 Poster: Mallows Models for Top-k Lists »
Flavio Chierichetti · Anirban Dasgupta · Shahrzad Haddadan · Ravi Kumar · Silvio Lattanzi -
2017 Poster: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Spotlight: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Poster: Affinity Clustering: Hierarchical Clustering at Scale »
Mohammadhossein Bateni · Soheil Behnezhad · Mahsa Derakhshan · MohammadTaghi Hajiaghayi · Raimondas Kiveris · Silvio Lattanzi · Vahab Mirrokni -
2016 Poster: Community Detection on Evolving Graphs »
Stefano Leonardi · Aris Anagnostopoulos · Jakub Łącki · Silvio Lattanzi · Mohammad Mahdian -
2014 Poster: Distributed Balanced Clustering via Mapping Coresets »
Mohammadhossein Bateni · Aditya Bhaskara · Silvio Lattanzi · Vahab Mirrokni -
2011 Oral: Reconstructing Patterns of Information Diffusion from Incomplete Observations »
Flavio Chierichetti · Jon Kleinberg · David Liben-Nowell -
2011 Poster: Reconstructing Patterns of Information Diffusion from Incomplete Observations »
Flavio Chierichetti · Jon Kleinberg · David Liben-Nowell