Introduzione agli Algoritmi di Approssimazione

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.