Google Research

Online Facility Location with Multiple Advice

  • Alessandro Panconesi
  • Flavio Chierichetti
  • Giuseppe Re
  • Matteo Almanza
  • Silvio Lattanzi
NeurIPS 2021 (to appear)

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work