Programma
Il corso si compone delle seguenti parti:
- Algoritmi di approssimazione per problemi NP-difficili;
- Algoritmi probabilistici e randomizzati;
- 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
Dalle dispense vanno esclusi i capitoli 1, 2, la dimostrazione di correttezza dell'algoritmo di Miller–Rabin, il capitolo 8.3, il capitolo 9.2 e il capitolo 14.
Per quanto riguarda gli algoritmi probabilistici e randomizzati, c'è il materiale nelle dispense più l'algoritmo di Karger (ma non il Karger–Stein).
Per quanto riguarda la parte di inapprossimabilità, dalla rassegna di Trevisan ci sono la definizione della classe PCP, i teoremi 1, 2, 3 (gli ultimi due, con dimostrazione) e i Claim 13 e 14 del capitolo 4.4 (riduzione diretta da PCP a insieme independente) con dimostrazione.
Per quanto riguarda la parte sulle strutture succinte, c'è il materiale nelle dispense, ad eccezione dei dettagli delle strutture o(n) per la 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. 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 . - Wikipedia fornisce una descrizione chiara dell'algoritmo di Karger.
- Ci sono anche i lucidi animati dell'esempio di esfoliazione (
peeling ). - Le dispense del corso coprono gli argomenti rimasti.