ALGORITMI PER IL PROBLEMA DEL MULTITAGLIO MINIMO SU GRAFI

Nel campo dell'ottimizzazione dei grafi, questa tesi analizza il problema del taglio minimo e due sue generalizzazioni: il problema del taglio multiway minimo e il problema del multitaglio minimo. A differenza del problema di partenza, queste due generalizzazioni sono NP-difficili, pertanto non ammettono algoritmi esatti per la loro risoluzione. Questa tesi si concentra quindi sull'analisi di algoritmi di approssimazione per la soluzione di questi problemi. In particolare, sono presentate diverse tecniche di ottimizzazione, inclusa quella di arrotondamento dei programmi lineari, per garantire soluzioni vicine all'ottimo. Infine, con l'obiettivo di sottolineare la rilevanza degli algoritmi introdotti anche in altri ambiti dell'ottimizzazione su grafi, sono presentati dei parallelismi tra il problema del multitaglio minimo su stelle e i problemi della copertura minima di vertici e del matching massimo su grafi qualsiasi.