SASSANO ANTONIO
(programma)
1. Sistemi di Indipendenza, definizioni, esempi e formulazioni lineari
2. Rilassamento Lagrangiano
3. Cammino Minimo con vincolo di “budget”
4. Problemi di Flusso “Multicommodity”
5. Algoritmi approssimati, Primale-Duale Approssimato
a. Applicazione al Set-Covering
b. Applicazione al Node-Covering
6. Problemi di “Network Design”
a. Metriche e Semimetriche
b. Teorema Giapponese (generalizzazione MFMC-property)
 • THE PRIMAL-DUAL METHOD FOR APPROXIMATION ALGORITHMS AND ITS APPLICATION TO NETWORK
DESIGN PROBLEMS, M. Goemans, D.P. Williamson;
• Lucidi del corso (auto-contenuti) disponibili (durante le lezioni) sul sito web http://www.dis.uniroma1.it/~sassano/
|
