Progetto e sperimentazione di un algoritmo per fair k-center clustering nel modello sliding window

L’obiettivo di questo lavoro è di misurare le prestazioni dell’algoritmo di Cappellotto e al. per la risoluzione di un problema di Fair K-Center nel modello Sliding Window, con particolare riguardo rispetto all’attuale stato dell’arte sviluppato da Chen e al. Mentre il problema di K-Center Clustering chiede di trovare, dato un insieme di punti presi da uno spazio metrico e un intero K, un sottoinsieme di centri tale per cui la distanza massima di un punto dall’insieme di centri sia minimizzata, nel problema FKC si ha il vincolo aggiuntivo che tale sottoinsieme deve essere un insieme indipendente per un matroide di partizione. Questo matroide, che può essere utilizzato per modellare vincoli di equità, è applicabile quando i punti di W sono divisibili in ℓ ≤ K gruppi, nel qual caso un insieme indipendente include al più ki punti per il gruppo i, con ki tali che la loro somma faccia K. Nel modello di calcolo Sliding Window in qualsiasi momento l’algoritmo deve essere in grado di calcolare in modo efficiente una soluzione a tale problema per l’insieme degli ultimi N punti dello stream. L’algoritmo di Cappellotto e al., il primo algoritmo che sia progettato specificatamente per tale modello, presenta un fattore di approssimazione pari a 3 + ϵ, dove 3 è la migliore approssimazione ottenibile sequenzialmente in tempo polinomiale e 0 < ϵ < 1 rappresenta un parametro di precisione definito dall’utente. Dimostreremo in questa tesi che tale algoritmo è sperimentalmente migliore in gran parte dei casi di utilizzo rispetto allo stato dell’arte, ed è altamente semplice da scalare per soddisfare necessità di prestazioni temporali e spaziali o di qualità.