Algoritmi approssimati per il problema di k-center su grafi sparsi

The thesis deals with the study and analysis of two sequential algorithms for the k-center problem on sparse graphs, which is an optimization problem consisting of selecting k vertices in a graph to minimize the maximum distance of any vertex from its nearest center. The first approach, inspired by the strategy for the k-center problem presented in [HS86], is based on computing a Maximal Independent Set of the graph’s vertices defined by a distance r, whose optimal value is found through a binary search in the interval (0, nD). This randomized algorithm guarantees an approximation factor of (2 + ε) with an expected running time of O((m+n log n) log n log n). The second approach examined is an approximate version of Gonzalez’s Algorithm from [GON85], called the α-approximate Gonzalez Algorithm. This approach iteratively builds the set of centers by selecting a vertex that is approximately at the maximum distance from the current set of centers, using a simple bucket-based data structure. The algorithm’s approximation factor is 2α and the average time complexity is O( [(m+n log n) log n log n]/ log α). Finally, the thesis discusses an alternative implementation using the potential of BFS for unweighted graphs and reflects on techniques to elevate the average time complexity to a high-probability complexity.

La tesi si occupa dello studio e dell'analisi di due algoritmi sequenziali per il problema di k-center su grafi sparsi, ossia un problema di ottimizzazione che consiste nel selezionare k vertici in un grafo in modo da minimizzare la massima distanza di qualsiasi vertice dal centro a esso più vicino. Il primo approccio, ispirato alla strategia per il problema di k-center presentata in proposto [HS86], si basa sul calcolo di un Maximal Independent Set dei vertici del grafo definito in base a una distanza r, il cui valore ottimale viene individuato attraverso una ricerca binaria nell'intervallo (0, nD). Questo algoritmo randomizzato garantisce un fattore di approssimazione di (2+ ε) con un tempo di esecuzione atteso di O((m+n log n)log n log n). Il secondo approccio esaminato è una versione approssimata dell'Algoritmo di Gonzalez tratto da [GON85], denominato Algoritmo di Gonzalez α-approssimato. Questo approccio costituisce iterativamente l'insieme dei centri, selezionando un vertice che si trova approssimativamente alla massima distanza dall'insieme corrente dei centri, utilizzando una semplice struttura dati basata su bucket. Il fattore di approssimazione dell'algoritmo è pari a 2α e la complessità temporale media è O([(m+n log n) log n log n] / log α). Infine la tesi discute un'implementazione alternativa utilizzando il potenziale della BFS per grafi non pesati e una riflessione sulle tecniche per elevare la complessità temporale media a una complessità con alta probabilità.