Network design with more traffic matrices
Prof. Gianpaolo Oriolo
UniversitÓ di Roma Tor Vergata
DEI - Seminar Room
February 22nd, 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.
Applied systems analysis and operations research