Università Roma Tre

INTRODUZIONE AI PROBLEMI DI OTTIMIZZAZIONE COMBINATORIA. ALGORITMI DI OTTIMIZZAZIONE. ANALISI DI COMPLESSITÀ DEGLI ALGORITMI. 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 -TSP. UN ALGORITMO 2-APPROSSIMATO PER IL -TSP. ALGORITMO DI CHRISTOFIDES. ALGORITMO 5/3-APPROSSIMATO PER IL TSPP. EURISTICHE PER IL TSP: A INSERIMENTO CON DIVERSI CRITERI DI SCELTA; MIGLIORATIVE (2-OPT EXCHANGE, 3-OPT, K-OPT, OR-OPT, LIN-KERNIGAN, TABU SEARCH, SIMULATED ANNEALING, ALG.GENETICI); ALGORITMI PER ISTANZE GEOMETRICHE (INVILUPPO CONVESSO, A SEZIONI, SWEEP).
IL PROBLEMA DI SCHEDULING SU MACCHINE PARALLELE. IL PROBLEMA DI BIN-PACKING.

• “LECTURE NOTES ON APPROXIMATION ALGORITHMS”, VOLUME I, R. MOTWANI.
• 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.
• SLIDE DELLE LEZIONI.