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.
Il progetto si pone a cavallo tra il campo degli algoritmi online, area di grande interesse per i problemi che le grandi realtà si trovano costrette ad affrontare oggigiorno vista la sempre crescente mole di dati, e il campo del machine learning, disciplina che ha contribuito ad avanzamenti qualitativi in innumerevoli campi. In particolare, riuscendo a fornire delle garanzie teoriche indipendenti dalla bontà dell¿oracolo (ossia il sistema di machine learning), si possono fornire algoritmi resistenti alla fallacità intrinseca del machine learning riuscendo allo stesso tempo a sfruttare questi sistemi quando riescono ad inferire correttamente.
Dato la recente proposta del modello OMLA preso in esame, il problema di facility location non è stato ancora oggetto di studi in questo nuovo ambito: una sua precisa caratterizzazione, sia teorica che pratica, aiuterebbe ad ampliarne la comprensione e fornirebbe nuovi strumenti per poter affrontare il problema in contesti online avendo a disposizione dati su cui allenare un modello di machine learning da usare come oracolo.