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
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 inMax3Sat avete dimostrato il PCP) e la versione di Hâstad con conseguente limitazione di inapprosimabilità ottima perMax3Sat . - Le dispense del corso coprono gli argomenti rimasti.