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.

Online Facility Location with Multiple Advice / Almanza, Matteo; Chierichetti, Flavio; Lattanzi, Silvio; Panconesi, Alessandro; Re, Giuseppe. - 34:(2021), pp. 4661-4673. (Intervento presentato al convegno Neurips 2021: Advances in Neural Information Processing Systems 34 tenutosi a Virtual Event).

Online Facility Location with Multiple Advice

Matteo Almanza;Flavio Chierichetti;Alessandro Panconesi;Giuseppe Re
2021

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.
2021
Neurips 2021: Advances in Neural Information Processing Systems 34
Clustering, Facility Location, Online Algorithms, Machine-Learned Advice, Online Clustering
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Online Facility Location with Multiple Advice / Almanza, Matteo; Chierichetti, Flavio; Lattanzi, Silvio; Panconesi, Alessandro; Re, Giuseppe. - 34:(2021), pp. 4661-4673. (Intervento presentato al convegno Neurips 2021: Advances in Neural Information Processing Systems 34 tenutosi a Virtual Event).
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1631201
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact