Network design with more traffic matrices

Network design with more traffic matrices

Prof. Gianpaolo Oriolo
UniversitÓ di Roma Tor Vergata

DEI - Sala Seminari
22 febbraio 2012


A crucial assumption in many network design problems is that the matrix of traffic demands is known in advance. Unfortunately, in several applications, communication patterns among terminals change over time. In such settings we do not deal with static demands, but a set D of non-simultaneous traffic matrices. Still, we would like to design a min-cost network that is able to support any traffic matrix that is from D.
In this paper, we discuss strategies for approaching this problem when D is given by a finite discrete list of traffic matrices. We present a poly(\log(k))-approximation based on recent results on vertex sparsifiers due to Leighton and Moitra, where k is the number of terminals, and settle complexity issues. We then focus on ring graphs, where we show the existence of a 4/3-approximation algorithm for the general problem, and an exact polynomial-time algorithm for the single source case.
This is joint work with Laura Sanita' and Rico Zenklusen.

Edoardo Amaldi

Area di ricerca:
Analisi applicata dei sistemi e ricerca operativa