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 8. 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.