8/1/08:
Implementazione di un meccanismo VCG per la determinazione del cammino minimo tra due nodi con complessita' temporale O(m + n logn). L'arco piu' vitale di un cammino minimo tra due nodi: Descrizione del problema; soluzioni banali. Algoritmo di Malik e studio della complessita'.
Slides: Meccanismo VCG per il cammino minimo tra due nodi.
10/1/08:
Implementazione di un meccanismo VCG per il problema della determinazione del minimo albero ricoprente in tempo O(m \alpha(m,n)). Il problema dell'analisi di sensitivita' di un minimo albero ricoprente: descrizione del problema e soluzione efficiente che utilizza il Transmuter. Definizione della funzione di Ackermann e la sua inversa. Proprieta' della funzione.
Slides: Meccanismo VCG per minimo albero ricoprente.
15/1/08 (4 ore):
Problemi di mechanism design non utilitari. Meccanismi one-parameter e relative proprieta'. Il problema dell'albero dei cammini minimi a singola sorgente nel protocollo unicast. Implementazione efficiente del meccanismo per il problema (non utilitario) della determinazione di un albero dei cammini minimi a singola sorgente con complessita' temporale O(m+ n logn).
Approfondimento: Esempio di determinazione dei pagamenti nel meccanismo one-parameter per il problema dell'albero dei cammini minimi.
Slides: Meccanismi one-parameter.
Slides:
Meccanismo one-parameter per il problema dell'albero dei cammini minimi..