Università Roma Tre

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.

[1] “Lecture Notes on Approximation Algorithms”, Volume I, R. Motwani.
[2] Dispense del prof. Agnetis (complessità, il problema del commesso viaggiatore, algoritmi euristici ).
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation,Combinatorial optimization problems and their approximability properties", Springer Verlag, 1999 (sito web del libro)
[4] Slide del docente disponibili sulla pagina web del corso.