Routing and Network Design With Robustness to Changing or Uncertain Traffic Demands

A new class of network design problems was introduced by Fingerhut et al. and independently by Duffield et al, to address, among other things, the issue of uncertainty in the demand matrix. The so-called hose model the term was coined in for demand matrices from was subsequently generalized to the polyhedral model by Ben-Ameur and Kerivin. In a different direction, Racke showed the existence of good randomized oblivious routings in all undirected graphs. This was followed by a proof of the polynomial time solvability of an optimal oblivious routing scheme. One can view the above developments in a common framework of robust optimization. This paper gives a survey of these developments and related work with the aim of providing a unified picture.