caa a22 4500 445805137 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9455-4 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9455-4 Dynamic vs. Oblivious Routing in Network Design [Elektronische Daten] [Navin Goyal, Neil Olver, F. BruceShepherd] Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare oblivious routing, where the routing between each terminal pair must be fixed in advance, to dynamic routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of Ω(log n) more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in (Chekuri, SIGACT News 38(3):106-128, 2007), and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns (Chekuri et al., Networks 50(1):50-54, 2007). Springer Science+Business Media, LLC, 2010 Robust network design nationallicence Oblivious routing nationallicence Dynamic routing nationallicence Goyal Navin Microsoft Reseach India, Bangalore, India aut Olver Neil Department of Mathematics and Statistics, McGill University, Montreal, Canada aut BruceShepherd F. Department of Mathematics and Statistics, McGill University, Montreal, Canada aut Algorithmica Springer-Verlag 61/1(2011-09-01), 161-173 0178-4617 61:1<161 2011 61 453 https://doi.org/10.1007/s00453-010-9455-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9455-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Goyal Navin Microsoft Reseach India, Bangalore, India aut NATIONALLICENCE 700 1- Olver Neil Department of Mathematics and Statistics, McGill University, Montreal, Canada aut NATIONALLICENCE 700 1- BruceShepherd F. Department of Mathematics and Statistics, McGill University, Montreal, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 161-173 0178-4617 61:1<161 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer