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.

Link identifier #identifier__4935-1Link identifier #identifier__53009-2Link identifier #identifier__136741-3Link identifier #identifier__149575-4
ffrati 04 March 2024