NeurIPS 2021poster39 citations
Online Facility Location with Multiple Advice
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, Giuseppe Re
Abstract
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.
ClusteringFacility LocationOnline AlgorithmsMachine-Learned AdviceOnline Clustering
BibTeX
@inproceedings{
almanza2021online,
title={Online Facility Location with Multiple Advice},
author={Matteo Almanza and Flavio Chierichetti and Silvio Lattanzi and Alessandro Panconesi and Giuseppe Re},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=A9HVNx1J8Pc}
}