Programma del corso di Ottimizzazione Combinatoria
Introduzione ai problemi di ottimizzazione combinatoria. Algoritmi di ottimizzazione. Analisi di complessità degli algoritmi.
Complessità: Problemi in forma di riconoscimento e di ottimizzazione. Classi P e NP. Riduzione fra problemi. Problemi NP-completi. Algoritmi pseudo-polinomiali.
Algoritmi di approssimazione. Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Algoritmi di approssimazione per il Vertex Cover: algoritmi greedy, algoritmo DFS, algoritmi basati sulla PL (arrotondamento e primale duale). Problemi di Knapsack: NP-completezza. Algoritmi di programmazione dinamica. Algoritmo greedy per il knapsack 0-1. Schema di approssimazione per il knapsack 0-1. Schema di approssimazione completamente polinomiale per il knapsack 0-1. Il problema del commesso viaggiatore (TSP): NP-completezza. Non-approssimabilità del TSP. Esempi di applicazioni. Il D-TSP. Un algoritmo 2-approssimato per il D-TSP. Algoritmo di Christofides. Algoritmo 5/3-approssimato per il TSPP. Problemi di scheduling su macchine parallele.
Algoritmi euristici: algoritmi costruttivi (euristiche per il TSP: a inserimento con diversi criteri di scelta, algoritmi per istanze geometriche); ricerca locale (per il TSP: 2-opt exchange, 3-opt, k-opt, OR-opt) ricerca locale a profondità variabile (Alg. Lin-Kernigan), tabu search, simulated annealing, alg.genetici, cenni ad altre metaeuristiche.
Cenni agli algoritmi online: algoritmi online, analisi competitiva, esempi.
Testi di Riferimento
“Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.
Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
Inoltre: