{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T20:15:48Z","timestamp":1680466548214},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T00:00:00Z","timestamp":1285632000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9455-4","type":"journal-article","created":{"date-parts":[[2010,9,27]],"date-time":"2010-09-27T16:14:52Z","timestamp":1285604092000},"page":"161-173","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic vs. Oblivious Routing in Network Design"],"prefix":"10.1007","volume":"61","author":[{"given":"Navin","family":"Goyal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Olver","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Bruce\u00a0Shepherd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,28]]},"reference":[{"key":"9455_CR1","first-page":"781","volume-title":"Proc. of IEEE FOCS","author":"I. Abraham","year":"2008","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: Proc. of IEEE FOCS, pp. 781\u2013790 (2008)"},{"key":"9455_CR2","first-page":"115","volume-title":"Proc. of IEEE FOCS","author":"M. Andrews","year":"2004","unstructured":"Andrews, M.: Hardness of buy-at-bulk network design. In: Proc. of IEEE FOCS, pp.\u00a0115\u2013124 (2004)"},{"key":"9455_CR3","unstructured":"Andrews, M.: Private communication (2010)"},{"issue":"1\u20132","key":"9455_CR4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0304-3975(99)00025-0","volume":"221","author":"Y. Bartal","year":"1999","unstructured":"Bartal, Y., Leonardi, S.: On-line routing in all-optical networks. Theor. Comput. Sci. 221(1\u20132), 19\u201339 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9455_CR5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/777313.777314","volume":"46","author":"W. Ben-Ameur","year":"2003","unstructured":"Ben-Ameur, W., Kerivin, H.: New economical virtual private networks. Commun. ACM 46(6), 69\u201373 (2003)","journal-title":"Commun. ACM"},{"issue":"3","key":"9455_CR6","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1145\/1324215.1324236","volume":"38","author":"C. Chekuri","year":"2007","unstructured":"Chekuri, C.: Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News 38(3), 106\u2013128 (2007)","journal-title":"SIGACT News"},{"issue":"1","key":"9455_CR7","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.20165","volume":"50","author":"C. Chekuri","year":"2007","unstructured":"Chekuri, C., Oriolo, G., Scutella, M.G., Shepherd, F.B.: Hardness of robust network design. Networks 50(1), 50\u201354 (2007)","journal-title":"Networks"},{"key":"9455_CR8","first-page":"1174","volume-title":"Proc. of ACM-SIAM SODA","author":"F. Eisenbrand","year":"2008","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Approximating connected facility location problems via random facility sampling and core detouring. In: Proc. of ACM-SIAM SODA, pp.\u00a01174\u20131183 (2008)"},{"issue":"3","key":"9455_CR9","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9455_CR10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1006\/jagm.1997.0866","volume":"24","author":"A.J. Fingerhut","year":"1997","unstructured":"Fingerhut, A.J., Suri, S., Turner, J.S.: Designing least-cost nonblocking broadband networks. J. Algorithms 24(2), 287\u2013309 (1997)","journal-title":"J. Algorithms"},{"key":"9455_CR11","first-page":"389","volume-title":"Proc. of ACM STOC","author":"A. Gupta","year":"2001","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proc. of ACM STOC, pp.\u00a0389\u2013398 (2001)"},{"issue":"3","key":"9455_CR12","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1236457.1236458","volume":"54","author":"A. Gupta","year":"2007","unstructured":"Gupta, A., Kumar, A., P\u00e1l, M., Roughgarden, T.: Approximation via cost sharing: Simpler and better approximation algorithms for network design. J. ACM 54(3), 11 (2007)","journal-title":"J. ACM"},{"issue":"4","key":"9455_CR13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/1290672.1290688","volume":"3","author":"M. Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M., Kleinberg, R., R\u00e4cke, H., Leighton, T.: Oblivious routing on node-capacitated and directed graphs. ACM Trans. Algorithms 3(4), 51 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9455_CR14","first-page":"284","volume-title":"Proc. of IEEE FOCS","author":"B.M. Maggs","year":"1997","unstructured":"Maggs, B.M., Meyer aud der\u00a0Heide, F., V\u00f6cking, B., Westerman, M.: Exploiting locality for networks of limited bandwidth. In: Proc. of IEEE FOCS, pp.\u00a0284\u2013293 (1997)"},{"key":"9455_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)"},{"key":"9455_CR16","first-page":"1097","volume-title":"Proc. of ACM-SIAM SODA","author":"N. Olver","year":"2010","unstructured":"Olver, N., Shepherd, F.B.: Approximability of robust network design. In: Proc. of ACM-SIAM SODA, pp.\u00a01097\u20131105 (2010)"},{"issue":"4","key":"9455_CR17","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C. Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245\u2013269 (2004)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9455-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9455-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9455-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:06Z","timestamp":1559137506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9455-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,28]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9455"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9455-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,28]]}}}