Programma

Il corso si compone delle seguenti parti:

• Algoritmi di approssimazione per problemi NP-difficili;
• Difficoltà di approssimazione dei problemi (in particolare, di alcuni affrontati nella prima parte);
• Cenni della teoria della complessità di approssimazione (in particolare, il PCP);
• Strutture dati succinte.

Per informazioni/chiarimenti, dopo avere letto alcune indicazioni di base potete scrivere al docente (Sebastiano Vigna).

Modalità d'esame

L'esame è orale. La data è fissata tramite appuntamento (gli appelli sono, di fatto, puramente nominali).

Per quanto riguarda la parte di approssimazione, il materiale è quello del capitolo 11 del libro di Jon Kleinberg e Éva Tardos, con l'esclusione del paragrafo avanzato 11.7, dell'analisi dell'algoritmo per Set Cover, dell'analisi del caso c > 1 del problema dei cammini disgiunti (“Designing and Analyzing a Pricing Algorithm”) e dell'analisi di Knapsack. È inoltre incluso l'algoritmo di Christofides e la dimostrazione dell'inapprossimabilità di Center Selection.

Per quanto riguarda la parte di inapprossimabilità, c'è il materiale nelle dispense, ad eccezione delle dimostrazioni del capitolo 7 e di MAXSNP. Dalla rassegna di Trevisan ci sono la definizione della classe PCP e i teoremi 1, 2, 3 (gli ultimi due, con dimostrazione).

Per quanto riguarda la parte sulle strutture succinte, c'è il materiale nelle dispense, ad eccezione dei dettagli delle strutture o(n) per rango e selezione, e dell'algoritmo broadword per la selezione.

Testi consigliati

• La parte di algoritmi di approssimazione è quasi interamente coperta dal capitolo 11 del libro di Jon Kleinberg e Éva Tardos (ecluso il paragrafo avanzato 11.7). Si noti che la discussione degli schemi di approssimazione polinomiale è un po' confusa—lo schema descritto per il problema dello zaino è uno schema di approssimazione pienamente polinomiale (cioè un FPTAS), dato che il tempo di calcolo è polinomiale in n e 1/ε. Ci sono degli ottimi lucidi di Kevin Wayne che elaborano parte del materiale del capitolo (con esempi), e contengono anche la dimostrazione di inapprossimabilità oltre il fattore 2 di Center Selection.
• Per l'algoritmo di Christofides c'è una chiara dispensa di Cornell.
• La rassegna di Luca Trevisan sull'inapprossimabilità contiene un introduzione storica al PCP, l'enunciato, il limite di inapprossimabilità di base di Max3Sat, il “PCP inverso” (se riuscite a creare un gap in Max3Sat avete dimostrato il PCP) e la versione di Hâstad con conseguente limitazione di inapprosimabilità ottima per Max3Sat.
• Le dispense del corso coprono gli argomenti rimasti.