L'algoritmo di Goemans-Williamson per il MaxCut: analisi teorica e implementazione computazionale

The MaxCut problem is one of the fundamental problems in graph theory and combinatorial optimization, characterized by the search for the maximum division of the vertices of a graph into two disjoint sets, such as to maximize the number of edges connecting the two groups. This NP-hard problem has numerous practical applications, such as the optimization of communication networks and data clustering. This thesis analyzes different MaxCut resolution techniques, with particular attention to the Goemans-Williamson algorithm, which exploits semidefinite programming and a randomized rounding technique based on probabilistic principles to obtain a guaranteed approximation factor of 0.878. The thesis also includes a Python implementation of the algorithm, analyzing its effectiveness on graphs of varying complexity and comparing it with other approximate methodologies. The goal is to demonstrate how the Goemans-Williamson algorithm is a powerful tool for tackling complex problems with an effective balance between precision and computational time.

Il problema del MaxCut è uno dei problemi fondamentali nella teoria dei grafi e nell'ottimizzazione combinatoria, caratterizzato dalla ricerca della massima divisione dei vertici di un grafo in due insiemi disgiunti, tale da massimizzare il numero di archi che collegano i due gruppi. Questo problema, NP-difficile, ha numerose applicazioni pratiche, come l'ottimizzazione delle reti di comunicazione e il clustering di dati. La presente tesi analizza diverse tecniche di risoluzione del MaxCut, con un'attenzione particolare all'algoritmo di Goemans-Williamson, che sfrutta la programmazione semidefinita e una tecnica di arrotondamento randomizzato basata su principi probabilistici per ottenere un fattore di approssimazione garantito di 0.878. La tesi include anche un'implementazione in Python dell'algoritmo, analizzando la sua efficacia su grafi di varia complessità e confrontandola con altre metodologie approssimative. L'obiettivo è dimostrare come l'algoritmo di Goemans-Williamson sia un potente strumento per affrontare problemi complessi con un bilancio efficace tra precisione e tempo computazionale.