{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:17:42Z","timestamp":1760015862092,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030394783"},{"type":"electronic","value":"9783030394790"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39479-0_7","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"89-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Upper Bound for the Ring Loading Problem"],"prefix":"10.1007","author":[{"given":"Karl","family":"D\u00e4ubel","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1109\/MCOM.2002.1006977","volume":"40","author":"R Ballart","year":"2002","unstructured":"Ballart, R., Ching, Y.C.: SONET: now it\u2019s the standard optical network. IEEE Commun. Mag. 40, 84\u201392 (2002)","journal-title":"IEEE Commun. Mag."},{"issue":"3","key":"7_CR2","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1137\/S0097539703423941","volume":"33","author":"AL Buchsbaum","year":"2004","unstructured":"Buchsbaum, A.L., Karloff, H., Kenyon, C., Reingold, N., Thorup, M.: OPT versus LOAD in dynamic storage allocation. SIAM J. Comput. 33(3), 632\u2013646 (2004). \nhttps:\/\/doi.org\/10.1137\/S0097539703423941","journal-title":"SIAM J. Comput."},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02110141","volume":"3","author":"S Cosares","year":"1994","unstructured":"Cosares, S., Saniee, I.: An optimization problem related to balancing loads on SONET rings. Telecommun. Syst. 3(2), 165\u2013181 (1994). \nhttps:\/\/doi.org\/10.1007\/BF02110141","journal-title":"Telecommun. Syst."},{"key":"7_CR4","unstructured":"D\u00e4ubel, K.: An improved upper bound for the ring loading problem (2019). \nhttps:\/\/arxiv.org\/abs\/1904.02119"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0167-6377(99)00031-0","volume":"25","author":"M Dell\u2019Amico","year":"1999","unstructured":"Dell\u2019Amico, M., Labb\u00e9, M., Maffioli, F.: Exact solution of the sonet ring loading problem. Oper. Res. Lett. 25(3), 119\u2013129 (1999). \nhttps:\/\/doi.org\/10.1016\/S0167-6377(99)00031-0","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single-source unsplittable flow problem. Combinatorica 19(1), 17\u201341 (1999). \nhttps:\/\/doi.org\/10.1007\/s004930050043","journal-title":"Combinatorica"},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/0095-8956(85)90046-2","volume":"39","author":"A Frank","year":"1985","unstructured":"Frank, A.: Edge-disjoint paths in planar graphs. J. Combin. Theory Ser. B 39(2), 164\u2013178 (1985). \nhttps:\/\/doi.org\/10.1016\/0095-8956(85)90046-2","journal-title":"J. Combin. Theory Ser. B"},{"key":"7_CR8","unstructured":"Costain, G., Kennedy, S., Meagher, C. (eds.): Bellairs 2007 - Combinatorial Optimization Workshop Open Problems (2007). \nhttp:\/\/www.math.mcgill.ca\/bshepherd\/Bellairs\/bellairs2007.pdf"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-61680-2_46","volume-title":"Algorithms \u2014 ESA \u201996","author":"J Gergov","year":"1996","unstructured":"Gergov, J.: Approximation algorithms for dynamic storage allocation. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 52\u201361. Springer, Heidelberg (1996). \nhttps:\/\/doi.org\/10.1007\/3-540-61680-2_46"},{"key":"7_CR10","unstructured":"Gergov, J.: Algorithms for compile-time memory optimization. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 907\u2013908. Society for Industrial and Applied Mathematics (1999)"},{"key":"7_CR11","volume-title":"SONET\/SDH","author":"W Goralski","year":"2002","unstructured":"Goralski, W.: SONET\/SDH, 3rd edn. McGraw-Hill Education, New York (2002)","edition":"3"},{"issue":"2","key":"7_CR12","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1002\/bltj.2047","volume":"2","author":"S Khanna","year":"1997","unstructured":"Khanna, S.: A polynomial time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J. 2(2), 36\u201341 (1997). \nhttps:\/\/doi.org\/10.1002\/bltj.2047","journal-title":"Bell Labs Tech. J."},{"issue":"4","key":"7_CR13","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/0401048","volume":"1","author":"HA Kierstead","year":"1988","unstructured":"Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1(4), 526\u2013530 (1988). \nhttps:\/\/doi.org\/10.1137\/0401048","journal-title":"SIAM J. Discrete Math."},{"issue":"2\u20133","key":"7_CR14","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(91)90011-P","volume":"88","author":"HA Kierstead","year":"1991","unstructured":"Kierstead, H.A.: A polynomial time approximation algorithm for dynamic storage allocation. Discrete Math. 88(2\u20133), 231\u2013237 (1991). \nhttps:\/\/doi.org\/10.1016\/0012-365X(91)90011-P","journal-title":"Discrete Math."},{"issue":"3","key":"7_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0305-0548(96)00028-7","volume":"24","author":"CY Lee","year":"1997","unstructured":"Lee, C.Y., Chang, S.G.: Balancing loads on SONET rings with integer demand splitting. Comput. Oper. Res. 24(3), 221\u2013229 (1997). \nhttps:\/\/doi.org\/10.1016\/S0305-0548(96)00028-7","journal-title":"Comput. Oper. Res."},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-540-75520-3_36","volume-title":"Algorithms \u2013 ESA 2007","author":"M Martens","year":"2007","unstructured":"Martens, M., Salazar, F., Skutella, M.: Convex combinations of single source unsplittable flows. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 395\u2013406. Springer, Heidelberg (2007). \nhttps:\/\/doi.org\/10.1007\/978-3-540-75520-3_36"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/S0895480199358709","volume":"14","author":"Y Myung","year":"2001","unstructured":"Myung, Y.: An efficient algorithm for the ring loading problem with integer demand splitting. SIAM J. Discrete Math. 14(3), 291\u2013298 (2001). \nhttps:\/\/doi.org\/10.1137\/S0895480199358709","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.orl.2003.08.001","volume":"32","author":"YS Myung","year":"2004","unstructured":"Myung, Y.S., Kim, H.G.: On the ring loading problem with demand splitting. Oper. Res. Lett. 32(2), 167\u2013173 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"7_CR19","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1287\/opre.45.1.148","volume":"45","author":"YS Myung","year":"1997","unstructured":"Myung, Y.S., Kim, H.G., Tcha, D.W.: Optimal load balancing on SONET bidirectional rings. Oper. Res. 45(1), 148\u2013152 (1997)","journal-title":"Oper. Res."},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s10878-007-9136-7","volume":"18","author":"Q Nong","year":"2009","unstructured":"Nong, Q., Yuan, J., Lin, Y.: The weighted link ring loading problem. J. Comb. Optim. 18(1), 38\u201350 (2009). \nhttps:\/\/doi.org\/10.1007\/s10878-007-9136-7","journal-title":"J. Comb. Optim."},{"issue":"31","key":"7_CR21","doi-asserted-by":"publisher","first-page":"2978","DOI":"10.1016\/j.tcs.2010.04.035","volume":"411","author":"Q Nong","year":"2010","unstructured":"Nong, Q., Cheng, T., Ng, C.: A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting. Theor. Comput. Sci. 411(31), 2978\u20132986 (2010). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2010.04.035","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"7_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480195294994","volume":"11","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A., Seymour, P., Winkler, P.: The ring loading problem. SIAM J. Discrete Math. 11(1), 1\u201314 (1998). \nhttps:\/\/doi.org\/10.1137\/S0895480195294994","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR23","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-540-76796-1_20","volume-title":"Research Trends in Combinatorial Optimization","author":"FB Shepherd","year":"2009","unstructured":"Shepherd, F.B.: Single-sink multicommodity flow with side constraints. In: Cook, W., Lov\u00e1sz, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 429\u2013450. Springer, Berlin (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-540-76796-1_20"},{"issue":"3, Ser. B","key":"7_CR24","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M Skutella","year":"2002","unstructured":"Skutella, M.: Approximating the single source unsplittable min-cost flow problem. Math. Program. 91(3, Ser. B), 493\u2013514 (2002). \nhttps:\/\/doi.org\/10.1007\/s101070100260","journal-title":"Math. Program."},{"issue":"1","key":"7_CR25","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1137\/14099588X","volume":"30","author":"M Skutella","year":"2016","unstructured":"Skutella, M.: A note on the ring loading problem. SIAM J. Discrete Math. 30(1), 327\u2013342 (2016). \nhttps:\/\/doi.org\/10.1137\/14099588X","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"7_CR26","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1287\/ijoc.8.3.235","volume":"8","author":"R Vachani","year":"1996","unstructured":"Vachani, R., Shulman, A., Kubat, P., Ward, J.: Multicommodity flows in ring networks. INFORMS J. Comput. 8(3), 235\u2013242 (1996). \nhttps:\/\/doi.org\/10.1287\/ijoc.8.3.235","journal-title":"INFORMS J. Comput."},{"key":"7_CR27","volume-title":"Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS","author":"JP Vasseur","year":"2004","unstructured":"Vasseur, J.P., Pickavet, M., Demeester, P.: Network Recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS. Morgan Kaufmann Publishers Inc., Burlington (2004)"},{"issue":"1","key":"7_CR28","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jalgor.2004.03.003","volume":"54","author":"BF Wang","year":"2005","unstructured":"Wang, B.F.: Linear time algorithms for the ring loading problem with demand splitting. J. Algorithms 54(1), 45\u201357 (2005). \nhttps:\/\/doi.org\/10.1016\/j.jalgor.2004.03.003","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39479-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T08:04:33Z","timestamp":1583741073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2019.ak.in.tum.de\/index.php\/menue-waoa\/waoa-overview","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}