Home » Archivo » Archvio 2010 » Algoritmi di approssimazione - 2010/2011

Laurea Magistrale

Salta il menu di secondo livello

Algoritmi di approssimazione - 6 CFU - A.A. 2010/2011

Insegnante

In Attesa di Assegnazione

Periodo

II anno - 1 trimestre | 18/10/2010 - 11/12/2010

Curriculum:

Ore: 40 Frontali, 0 Laboratorio, 8 Esercizi

Torna su ▲

Programma del Corso

Algoritmi on-line.
- Analisi competitiva per gli algoritmi on-line.
- Paginazione: Competitività di LRU. Algoritmo off-line ottimo.
Limite inferiore per la competitività degli algoritmi on-line.
Algoritmi on-line randomizzati. Analisi di MARKING. Limite
inferiore per algoritmi on-line randomizzati. Tipi di avversari
e competitività contro i vari tipi di avversari. Analisi di RANDOM.
- K server:
Riassunto dei risultati noti e algoritmi on-line ingenui.
ATTIVI, un algoritmo k-competitivo sugli alberi. RWALK,
un algoritmo k-competitivo sugli spazi metrici resistivi.
L'algoritmo della funzione lavoro (2k-1)-competitivo su
spazi metrici generali (senza la dimostrazione della competitività).

Algoritmi di approssimazione.
- Risultati negativi:
Caratterizzazioni delle classi P ed NP in termini di verificatori.
Teorema di Cook: 3SAT è NP-completo (senza dimostrazione).
Riduzione di 3SAT a 3COLOR.
Verificatori probabilistici. Il teorema PCP di Arora (senza
dimostrazione). Caratterizzazione di Arora della classe NP in
termini di verificatori probabilistici. Risultati di non
approssimabilità derivati dal teorema di Arora. Caratterizzazione
di Faggin della classe NP e problemi MAX-SNP-completi.
- Progetto di algoritmi approssimati:
Algoritmo di Cristofides per il problema TSP euclideo.
La tecnica del rilassamento. Rilassamento di tipo LP.
Il problema del minimo ricoprimento di vertici. Algoritmi
di Hochbaum e di Bar-Yehuda ed Even.
Il metodo primale-duale. Il problema del matching perfetto
di costo minimo. Algoritmo di Goemans e Williamson.
Uso di rilassamenti non lineari. Il problema del taglio massimo.
L'algoritmo 0.878.
- Gli schemi di approssimazione e le classi PAS, FPAS, PAAS ed FPAAS.
Relazione tra i due problemi dell'impacchettamento e della schedulazione.
Comportamento diverso dei due problemi rispetto all'approssimabilità.
Un PAS per il problema della schedulazione.

Prerequisiti: Computabilità e Algoritmi

Propedeuticità:

Ausili Didattici: - -

Testi di Riferimento: Vijay V Vazirani.
Approximation Algorithms.
Ed. Springer.

Torna su ▲