Ricerc@Sapienza

Nel problema di facility location vogliamo fornire un servizio a una serie di utenti, minimizzando il costo dovuto all'apertura di punti in grado di fornire il servizio, detti fornitori, e alle distanze fra gli utenti e il loro fornitore più vicino.
Tale schema è alla base di molti problemi di estrema rilevanza da un punto di vista pratico, legati al fornire servizi (supermercati, connessione internet, servizi postali) a una rete di utenti nel modo più efficiente possibile.
Considereremo sempre utenti e fornitori come punti generici in uno spazio metrico, facendo quindi riferimento al problema noto come "metric facility location". Nella versione classica di questo problema, utenti e fornitori sono dati come punti in input e si chiede di determinare una configurazione ottimale di fornitori. Nella versione online i punti da servire vengono forniti in input singolarmente e progressivamente nel tempo. All'arrivo di ogni utente occorre effettuare una scelta irreversibile: associarlo ad un fornitore precedentemente aperto oppure crearne uno nuovo per servire tale punto.
Diversi algoritmi sono stati formulati per questo problema. Tuttavia, per quanto riguarda la versione online, Fotakis ha dimostrato l'impossibilità di fornire un'approssimazione costante della soluzione ottima sotto l'assunzione P!=NP.
D'altra parte, in molti contesti applicativi sono disponibili strumenti di Machine Learning e Data Analysis che permettono di fare previsioni sulle future istanze di input. Da qui nasce il modello matematico OMLA (Online with Machine Learned Advice) di Vassilvitskii e Lykouris. Tramite tale modello ci si propone di analizzare formalmente l'impiego di oracoli all'interno di problemi algoritmici online.
Il nostro progetto si pone l'obiettivo di studiare algoritmi deterministici e randomici per il problema online facility location nel modello OMLA. Al riguardo, vi sono sia strade promettenti per un esito positivo dal punto di vista teorico che vibrante interesse applicativo.