Introduzione agli Algoritmi di Approssimazione

Questa pagina descrive il corso di dottorato “Introduzione agli Algoritmi di Approssimazione“, tenuto dalla Prof. Gaia Nicosia.

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.