Routing and network design with robustness to changing or uncertain traffic demands
Chandra Chekuri · ACM SIGACT News · 2007
A new class of network design problems were introduced by Fingerhut et al. [26], and independently by Duffield et al. [20], to address, among other things, the issue of uncertainty in the demand matrix. The so-called hose model (the term was coined in [20]) for demand matrices from [26, 20] was subsequently generalized to the polyhedral model by Ben-Ameur and Kerivin [11, 10]. In a different direction, Räacke [51] 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 [7]. One can view the above developments in a common framework of robust optimization. We give a survey of these developments and related work with the aim of providing a unified picture. We also highlight the remaining open problems.