Matroid-center clustering in sliding windows

In this thesis, we study the Matroid Center problem which, given a set of points from a metric space and an integer < ||, requires to find a subset of of centers such that the maximum distance of a point of from is minimized, and is an independent set of a specified matroid. In particular, we consider the partition matroid, which can be used to model fairness constraints, and the more general transversal matroid. For both matroids we devise the first approximation streaming algorithms under the sliding window model, which, at any time, are able to efficiently compute a solution to Matroid Center for the latest window of points of the stream. The algorithms exhibit a (3+)-approximate ratio, where 3 is the best approximation attainable in sequential polynomial time and in (0, 1) is a user-defined accuracy parameter. The analysis of the algorithms is carried out in terms of the dimensionality of the data, and it shows that, for low dimensional data the required working memory and processing time are asymptotically and significantly smaller than the window size.

In questa tesi, studiamo il problema del Matroid Center, il cui obiettivo è trovare, dato un insieme di punti presi da uno spazio metrico e un intero < ||, un sottoinsieme di di centri tale per cui la distanza massima di un punto di da sia minimizzata e sia un insieme indipendente di una matroide specificata. In particolare, esaminiamo i casi relativi alla matroide di partizione, che può essere utilizzata per modellare vincoli di equità, e alla più generale matroide trasversale. Per entrambe le matroidi costruiamo i primi algoritmi di approssimazione per il modello di calcolo a finestre scorrevoli, i quali, in qualsiasi momento, sono in grado di calcolare in modo efficiente una soluzione del Matroid Center per l’ultima finestra di punti dello stream. Questi algoritmi presentano un fattore di approssimazione pari a (3+), dove 3 è la migliore approssimazione ottenibile sequenzialmente in tempo polinomiale e in (0, 1) rappresenta un parametro di precisione definito dall’utente. L’analisi degli algoritmi viene effettuata in termini di dimensionalità dei dati e mostra che, per dati a bassa dimensionalità, la memoria di lavoro richiesta e il tempo di elaborazione sono asintoticamente e significativamente inferiori alla dimensione della finestra.