Questa pagina descrive il corso di dottorato “Introduzione agli Algoritmi di Approssimazione“, tenuto dalla Prof. Gaia Nicosia.
Date
- lunedì 11 marzo, 11:00-13:30
- martedì 12 marzo, 9:00-13:30
- giovedì 14 marzo, 9:00-13:30
Luogo
Sala riunioni informatica (DIA 1.10), primo piano edificio ex-OMI
Contenuti
Introduzione agli algoritmi di approssimazione. Misure di approssimazione assoluta e relativa. Algoritmi di approssimazione per il problema di Vertex Cover. Classi di approssimazione: NPO, APX, PTAS, FPTAS, PO. Schema di approssimazione polinomiale per il Knapsack 0-1. Algoritmo di programmazione dinamica per knapsack 0-1. Schema di approssimazione completamente polinomiale per il Knapsack 0-1. Non approssimabilità del TSP. Algoritmi di approssimazione per il TSP metrico.