Ricerc@Sapienza

In questo progetto consideriamo diversi aspetti dello studio di
algoritmi su grafi: (1) la sintesi di nuovi algoritmi per problemi
importanti; (2) l'analisi degli algoritmi noti e i lori limiti di
efficienza; (3) l'implementazione distribuita di algoritmi per
applicazioni dove tipicamente i grafi sono enormi.

Il progetto si occupa della sintesi di algoritmi per importanti
parametri come la vitalità e la centralità di elementi del grafo,
parametri calcolati rispetto a problemi come quello del flusso massimo
o dei cammini minimi. Tipicamente questi problemi hanno complessità
quadratica, che non è accettabile per grafi di grandi dimensioni.

L'analisi teorica di algoritmi per problemi sui grafi è basata
principalmente sulla proof complexity ovvero sullo studio dei
certificati di insoddisfacibilità che questi algoritmi producono.
Questi certificati vengono studiati per dare limiti inferiori
all'efficienza dei corrispondenti algoritmi (e.g. se il certificato
deve essere molto lungo, l'algoritmo deve impiegare molto tempo
a produrlo). Questi certificati possono anche essere usati per
verificare la correttezza delle computazioni.

Per la parte sperimentale si considerano i grafi che rappresentano le
interazioni tra gruppi di proteine. Tipicamente questi grafi sono
enormi e non possono essere memorizzati su un singolo calcolatore, il
che esclude la possibilità di analizzali con gli algoritmi sequenziali
presenti in letteratura. Qui cerchiamo di impostare versioni
distribuite di questi algoritmi nell'architettura MarReduce, oppure di
ideare nuovi algoritmi adatti al contesto.