Approximation Algorithms for Network Problems II

Soggetto ed obiettivi

In un tipico problema di ottimizzazione ci viene dato (in modo implicito) un insieme di soluzioni ammissibili. Il nostro scopo è selezionare una soluzione ammissibile che ottimizzi una data funzione obiettivo. Molti dei problemi di ottimizzazione che occorre risolvere in pratica riguardano applicazioni su reti, e fra questi molti problemi rilevanti sono NP-hard. Questo rende improbabile l'esistenza di un algoritmo efficiente per la loro soluzione (nel caso pessimo). In questo frangente, ha senso sviluppare degli algoritmi di approssimazione, ossia degli algoritmi efficienti per calcolare una soluzione di costo vicino all'ottimo. L'obiettivo di alto livello di questo progetto è di sviluppare algoritmi di approssimazione più accurati, cioè in grado di produrre soluzioni più vicine all’ottimo.

Più in dettaglio, ci occuperemo di una famiglia di problemi di rete in cui occorre connettere gruppi di nodi a costo minimo, possibilmente con connettività maggiore di uno in modo da essere robusti rispetto a guasti di rete. Ci interessano anche alcuni problemi di impacchettamento di traffico in reti con capacità limitata. In questo caso un tipico obiettivo è massimizzare il profitto derivante dal traffico instradato con successo. Infine considereremo problemi di pricing, dove occorre vendere risorse di rete a potenziali clienti massimizzando il profitto totale e rispettando opportuni vincoli.

Contesto socio-scientifico

Il progetto si occupa di ricerca di base. Storicamente, lo sviluppo di algoritmi di approssimazione ha portato ad una migliore comprensione delle proprietà strutturali delle soluzioni ottime dei problemi studiati e anche delle caratteristiche specifiche delle istanze che le rendono difficili (o facili) da risolvere in modo ottimo o quasi. Inoltre, in questa area di ricerca sono state sviluppate nuove tecniche euristiche. Questo tipicamente ha un impatto sulla soluzione pratica dei problemi su medio-lungo termine.