Próxima Charla del DC: Viernes 15/4/2011 - 14 hs. Gianpaolo Oriolo - Università di Roma "Tor Vergata", Roma, Italia. Robust Network Design
A crucial assumption in many network design problems is that of knowing the traffic demand in advance. Unfortunately, in several applications, communication patterns change over time, and therefore we are not given a single static traffic matrix, but a set D of non-simultaneous traffic demands. Still, we would like to design a min-cost network that is able to support any traffic demand that is from D.
In this talk, we discuss strategies for approaching this problem when D is either given implicitly, i.e., it is described by a set of linear inequalities, or explicitly, i.e. it is described by a finite set of traffic matrices. We settle some complexity results, and give some exact and approximation algorithms for some relevant cases.
The presentation is meant to be introductory to the subject and part of it will be done on the blackboard.
