{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:56Z","timestamp":1761611216897,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>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\u00e4acke [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].<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1324215.1324236","type":"journal-article","created":{"date-parts":[[2007,12,7]],"date-time":"2007-12-07T19:19:01Z","timestamp":1197055141000},"page":"106-129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Routing and network design with robustness to changing or uncertain traffic demands"],"prefix":"10.1145","volume":"38","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]}],"member":"320","published-online":{"date-parts":[[2007,9]]},"reference":[{"volume-title":"Algorithms and Applications. Prentice Hall","year":"1993","author":"Ahuja R.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v49:1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863991"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.010"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00025-0"},{"key":"e_1_2_1_10_1","first-page":"283","volume":"3","author":"Ben-Ameur W.","year":"2005","journal-title":"Routing of Uncertain Demands. Optimization and Engineering"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/777313.777314"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777418"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796406"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.15"},{"volume-title":"Proc. of ACM-SIAM SODA","year":"2007","author":"Chekuri C.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007383"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060618"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v50:1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301447"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316209"},{"volume-title":"Proc. of ACM-SIAM SODA, 928--932","year":"2005","author":"Eisenbrand F.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654827"},{"key":"e_1_2_1_23_1","unstructured":"F. Grandoni V. Kaibel G. Oriolo and M. Skutella. Unpublished manuscript 2005.  F. Grandoni V. Kaibel G. Oriolo and M. Skutella. Unpublished manuscript 2005."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354650"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0866"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109625"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796579"},{"key":"e_1_2_1_31_1","unstructured":"A. Gupta. Personal communication 2004.  A. Gupta. Personal communication 2004."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780597"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109665"},{"volume-title":"Proc. ACM-SIAM SODA, 782--790","year":"2005","author":"Hajiaghayi M.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060619"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777419"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/050626259"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.09.005"},{"volume-title":"Proc. of IEEE FOCS","year":"2000","author":"Karger D.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"volume-title":"HotNets III","year":"2004","author":"Kodialam M.","key":"e_1_2_1_42_1"},{"volume-title":"Maximum Throughput Routing of Traffic in the Hose Model Proc. of IEEE INFOCOM","year":"2006","author":"Kodialam M.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"volume-title":"Proc. of INOC, 258--264","year":"2005","author":"Lemar\u00e9chal C.","key":"e_1_2_1_45_1"},{"volume-title":"Proc. of IEEE FOCS, 284--293","year":"1997","author":"Maggs B.","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073996"},{"key":"e_1_2_1_48_1","unstructured":"H. Nagesh V. Poosala S. Sengupta M. Alicherry and V. Kumar. NetSwitch: Load-balanced Data-over-Optical Architecture for Mesh Networks. Lucent Technical Memorandum ITD-04-45867F 2004.  H. Nagesh V. Poosala S. Sengupta M. Alicherry and V. Kumar. NetSwitch: Load-balanced Data-over-Optical Architecture for Mesh Networks. Lucent Technical Memorandum ITD-04-45867F 2004."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/OFC.2005.192558"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1364\/JON.5.000320"},{"volume-title":"Minimizing Congestion in General Networks. Proc. of IEEE FOCS, 43--52","year":"2002","author":"R\u00e4cke H.","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/647909.740164"},{"volume-title":"Springer","year":"2003","author":"Schrijver A.","key":"e_1_2_1_53_1"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802479"},{"volume-title":"HotNets III","year":"2004","author":"Zhang-Shen R.","key":"e_1_2_1_56_1"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324215.1324236","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1324215.1324236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:58:25Z","timestamp":1750258705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1324215.1324236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["10.1145\/1324215.1324236"],"URL":"https:\/\/doi.org\/10.1145\/1324215.1324236","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2007,9]]},"assertion":[{"value":"2007-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}