Un algoritmo pienamente combinatorico per il problema del robust matroid center

Il Robust Matroid Center è una generalizzazione del problema del k-center che combina due aspetti fondamentali: la robustezza rispetto agli outliers e l'imposizione di vincoli strutturali espressi tramite un matroide. Questa tesi analizza in dettaglio l'algoritmo combinatorio proposto da Anegg et al. che fornisce una 5-approssimazione per il problema tramite una semplice procedura greedy, migliorando la precedente 7-approssimazione di Chen et al. Dopo aver introdotto i concetti preliminari di spazio metrico, matroide, matroide di Rado e intersezione di matroidi, viene presentato un percorso che porta alla formulazione formale del problema di interesse e viene mostrato lo stato dell'arte prima di questo algoritmo. Uno dei punti fondamentali di questa tesi è l'analisi del rilassamento del vincolo matroidale attraverso il matroide di Rado M_relax, che consente di posticipare la scelta dei centri effettivi massimizzando la flessibilità nella selezione. Viene illustrata la strategia greedy, corredata da esempi, e dimostrata la correttezza tramite un argomento di scambio basato sul matroide ausiliario M_ext. Uno degli obiettivi della tesi è di favorire la comprensione dell'algoritmo e della sua analisi tramite la motivazione più dettagliata delle scelte progettuali e l'esplicitazione di alcune implicazioni che sono meno evidenti nel paper di Anegg et al. Infine, viene mostrato come trovare la 5-approssimazione della soluzione ottima e viene effettuata l'analisi di complessità. La trattazione si conclude con una discussione dei vantaggi, delle limitazioni e di possibili sviluppi futuri per estendere l'approccio a scenari più complessi.