{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T16:21:00Z","timestamp":1772468460848,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Vidi.189.087"],"award-info":[{"award-number":["016.Vidi.189.087"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1955785"],"award-info":[{"award-number":["CCF-1955785"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006953"],"award-info":[{"award-number":["CCF-2006953"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2224718"],"award-info":[{"award-number":["CCF-2224718"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2121744"],"award-info":[{"award-number":["CCF-2121744"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1845146"],"award-info":[{"award-number":["CCF-1845146"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given <jats:italic>m<\/jats:italic> resources and <jats:italic>n<\/jats:italic> requests; each request has multiple possible <jats:italic>configurations<\/jats:italic>, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the <jats:italic>makespan<\/jats:italic>: the load of the most-loaded resource. In the stochastic setting, the amount by which a configuration increases the resource load is uncertain until the configuration is chosen, but we are given a probability distribution. We develop both offline and online algorithms for configuration balancing with stochastic requests. When the requests are known offline, we give a non-adaptive policy for configuration balancing with stochastic requests that <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\frac{\\log m}{\\log \\log m})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mrow>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>m<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>m<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-approximates the optimal adaptive policy, which matches a known lower bound for the special case of load balancing on identical machines. When requests arrive online in a list, we give a non-adaptive policy that is <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log m)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> competitive. Again, this result is asymptotically tight due to information-theoretic lower bounds for special cases (e.g., for load balancing on unrelated machines). Finally, we show how to leverage adaptivity in the special case of load balancing on <jats:italic>related<\/jats:italic> machines to obtain a constant-factor approximation offline and an <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log \\log m)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-approximation online. A crucial technical ingredient in all of our results is a new structural characterization of the optimal adaptive policy that allows us to limit the correlations between its decisions.\n<\/jats:p>","DOI":"10.1007\/s10107-024-02132-w","type":"journal-article","created":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T06:03:01Z","timestamp":1723096981000},"page":"243-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Configuration balancing for stochastic requests"],"prefix":"10.1007","volume":"210","author":[{"given":"Franziska","family":"Eberle","sequence":"first","affiliation":[]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Nicole","family":"Megow","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5037-4885","authenticated-orcid":false,"given":"Rudy","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,8]]},"reference":[{"key":"2132_CR1","doi-asserted-by":"publisher","unstructured":"Eberle, F., Gupta, A., Megow, N., Moseley, B., Zhou, R.: Configuration balancing for stochastic requests. In: Integer Programming and Combinatorial Optimization, IPCO 2023, pp. 127\u2013141. https:\/\/doi.org\/10.1007\/978-3-031-32726-1_10","DOI":"10.1007\/978-3-031-32726-1_10"},{"issue":"2","key":"2132_CR2","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. J. SIAM Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"J. SIAM Appl. Math."},{"issue":"4","key":"2132_CR3","doi-asserted-by":"publisher","first-page":"3317","DOI":"10.1287\/moor.2021.1239","volume":"47","author":"S Perez-Salazar","year":"2022","unstructured":"Perez-Salazar, S., Singh, M., Toriello, A.: Adaptive bin packing with overflow. Math. Oper. Res. 47(4), 3317\u20133356 (2022). https:\/\/doi.org\/10.1287\/moor.2021.1239","journal-title":"Math. Oper. Res."},{"key":"2132_CR4","doi-asserted-by":"publisher","unstructured":"Leighton, T., Rao, S., Srinivasan, A.: Multicommodity flow and circuit switching. In: HICSS, pp. 459\u2013465 (1998). https:\/\/doi.org\/10.1109\/HICSS.1998.649241","DOI":"10.1109\/HICSS.1998.649241"},{"issue":"3","key":"2132_CR5","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486\u2013504 (1997). https:\/\/doi.org\/10.1145\/258128.258201","journal-title":"J. ACM"},{"issue":"2","key":"2132_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18(2), 221\u2013237 (1995). https:\/\/doi.org\/10.1006\/jagm.1995.1008","journal-title":"J. Algorithms"},{"key":"2132_CR7","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993). https:\/\/doi.org\/10.1007\/BF01585178","journal-title":"Math. Program."},{"issue":"1","key":"2132_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1287\/moor.2019.1049","volume":"46","author":"A Gupta","year":"2021","unstructured":"Gupta, A., Kumar, A., Nagarajan, V., Shen, X.: Stochastic load balancing on unrelated machines. Math. Oper. Res. 46(1), 115\u2013133 (2021). https:\/\/doi.org\/10.1287\/moor.2019.1049","journal-title":"Math. Oper. Res."},{"key":"2132_CR9","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","volume":"17","author":"EML Beale","year":"1955","unstructured":"Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. R. Stat. Soc. Ser. B Methodol. 17, 173\u2013184194203 (1955)","journal-title":"J. R. Stat. Soc. Ser. B Methodol."},{"key":"2132_CR10","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/mnsc.1040.0261","volume":"1","author":"GB Dantzig","year":"1955","unstructured":"Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1, 197\u2013206 (1955). https:\/\/doi.org\/10.1287\/mnsc.1040.0261","journal-title":"Manag. Sci."},{"issue":"8","key":"2132_CR11","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1002\/nav.10092","volume":"50","author":"S Dye","year":"2003","unstructured":"Dye, S., Stougie, L., Tomasgard, A.: The stochastic single resource service-provision problem. Naval Res. Logist. 50(8), 869\u2013887 (2003). https:\/\/doi.org\/10.1002\/nav.10092","journal-title":"Naval Res. Logist."},{"issue":"6","key":"2132_CR12","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of lp-based priority policies. J. ACM 46(6), 924\u2013942 (1999). https:\/\/doi.org\/10.1145\/331524.331530","journal-title":"J. ACM"},{"key":"2132_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/11538462_22","volume":"3624","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Chekuri, C., P\u00e1l, M.: Sampling bounds for stochastic optimization. Proceed. APPROX. LNCS 3624, 257\u2013269 (2005). https:\/\/doi.org\/10.1007\/11538462_22","journal-title":"Proceed. APPROX. LNCS"},{"issue":"5","key":"2132_CR14","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1137\/080732250","volume":"40","author":"A Gupta","year":"2011","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Sinha, A.: Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. SIAM J. Comput. 40(5), 1361\u20131401 (2011). https:\/\/doi.org\/10.1137\/080732250","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2132_CR15","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/100789269","volume":"41","author":"C Swamy","year":"2012","unstructured":"Swamy, C., Shmoys, D.B.: Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput. 41(4), 975\u20131004 (2012). https:\/\/doi.org\/10.1137\/100789269","journal-title":"SIAM J. Comput."},{"key":"2132_CR16","doi-asserted-by":"publisher","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: Proceedings of SODA, pp. 1647\u20131665 (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.127","DOI":"10.1137\/1.9781611973082.127"},{"issue":"4","key":"2132_CR17","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1287\/moor.1080.0330","volume":"33","author":"BC Dean","year":"2008","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33(4), 945\u2013964 (2008). https:\/\/doi.org\/10.1287\/moor.1080.0330","journal-title":"Math. Oper. Res."},{"key":"2132_CR18","doi-asserted-by":"publisher","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. In: Ostrovsky, R. (ed.) Proceedings of FOCS, pp. 827\u2013836 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.48","DOI":"10.1109\/FOCS.2011.48"},{"issue":"3","key":"2132_CR19","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/moor.2017.0884","volume":"43","author":"W Ma","year":"2018","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3), 789\u2013812 (2018). https:\/\/doi.org\/10.1287\/moor.2017.0884","journal-title":"Math. Oper. Res."},{"key":"2132_CR20","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990). https:\/\/doi.org\/10.1007\/BF01585745","journal-title":"Math. Program."},{"issue":"1","key":"2132_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/S0097539797329142","volume":"30","author":"JM Kleinberg","year":"2000","unstructured":"Kleinberg, J.M., Rabani, Y., Tardos, \u00c9.: Allocating bandwidth for Bursty connections. SIAM J. Comput. 30(1), 191\u2013217 (2000). https:\/\/doi.org\/10.1137\/S0097539797329142","journal-title":"SIAM J. Comput."},{"key":"2132_CR22","doi-asserted-by":"publisher","unstructured":"Molinaro, M.: Stochastic $${\\mathcalligra{l}}$$p load balancing and moment problems via the l-function method. In: Proceedings of SODA, pp. 343\u2013354 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.22","DOI":"10.1137\/1.9781611975482.22"},{"key":"2132_CR23","doi-asserted-by":"publisher","unstructured":"Ibrahimpur, S., Swamy, C.: Approximation algorithms for stochastic minimum-norm combinatorial optimization. In: Proceedings of FOCS, pp. 966\u2013977 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00094","DOI":"10.1109\/FOCS46700.2020.00094"},{"key":"2132_CR24","doi-asserted-by":"publisher","unstructured":"Sagnol, G., Schmidt genannt Waldschmidt, D.: restricted adaptivity in stochastic scheduling. In: Proceedings of ESA. LIPIcs, vol. 204, pp. 79\u201317914 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.79","DOI":"10.4230\/LIPIcs.ESA.2021.79"},{"issue":"2","key":"2132_CR25","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1287\/moor.2019.0999","volume":"45","author":"V Gupta","year":"2020","unstructured":"Gupta, V., Moseley, B., Uetz, M., Xie, Q.: Greed works - online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2), 497\u2013516 (2020). https:\/\/doi.org\/10.1287\/moor.2019.0999","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2132_CR26","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.1060.0201","volume":"31","author":"N Megow","year":"2006","unstructured":"Megow, N., Uetz, M., Vredeveld, T.: Models and algorithms for stochastic online scheduling. Math. Oper. Res. 31(3), 513\u2013525 (2006). https:\/\/doi.org\/10.1287\/moor.1060.0201","journal-title":"Math. Oper. Res."},{"issue":"6","key":"2132_CR27","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/331524.331530","volume":"46","author":"RH M\u00f6hring","year":"1999","unstructured":"M\u00f6hring, R.H., Schulz, A.S., Uetz, M.: Approximation in stochastic scheduling: the power of lp-based priority policies. J. ACM 46(6), 924\u2013942 (1999). https:\/\/doi.org\/10.1145\/331524.331530","journal-title":"J. ACM"},{"key":"2132_CR28","doi-asserted-by":"publisher","unstructured":"Schulz, A.S.: Stochastic online scheduling revisited. In: Yang, B., Du, D., Wang, C.A. (eds.) Proceedings of COCOA. LNCS, vol. 5165, pp. 448\u2013457 (2008). https:\/\/doi.org\/10.1007\/978-3-540-85097-7_42","DOI":"10.1007\/978-3-540-85097-7_42"},{"issue":"4","key":"2132_CR29","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1137\/S0097539702415007","volume":"34","author":"M Skutella","year":"2005","unstructured":"Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM J. Comput. 34(4), 788\u2013802 (2005). https:\/\/doi.org\/10.1137\/S0097539702415007","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2132_CR30","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.2015.0757","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella, M., Sviridenko, M., Uetz, M.: Unrelated machine scheduling with stochastic processing times. Math. Oper. Res. 41(3), 851\u2013864 (2016). https:\/\/doi.org\/10.1287\/moor.2015.0757","journal-title":"Math. Oper. Res."},{"key":"2132_CR31","doi-asserted-by":"publisher","unstructured":"Im, S., Moseley, B., Pruhs, K.: Stochastic scheduling of heavy-tailed jobs. In: Mayr, E.W., Ollinger, N. (eds.) Proceedings of STACS, vol. 30, pp. 474\u2013486 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.474","DOI":"10.4230\/LIPIcs.STACS.2015.474"},{"key":"2132_CR32","doi-asserted-by":"publisher","unstructured":"Azar, Y.: On-line load balancing. In: Online Algorithms. LNCS, vol. 1442, pp. 178\u2013195 (1996). https:\/\/doi.org\/10.1007\/BFb0029569","DOI":"10.1007\/BFb0029569"},{"issue":"1","key":"2132_CR33","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P Berman","year":"2000","unstructured":"Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. J. Algorithms 35(1), 108\u2013121 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1070","journal-title":"J. Algorithms"},{"key":"2132_CR34","doi-asserted-by":"publisher","unstructured":"Im, S., Kell, N., Panigrahi, D., Shadloo, M.: Online load balancing on related machines. In: Proceedings of STOC, pp. 30\u201343 (2018). https:\/\/doi.org\/10.1145\/3188745.3188966","DOI":"10.1145\/3188745.3188966"},{"issue":"1","key":"2132_CR35","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/17M111835X","volume":"48","author":"S Im","year":"2019","unstructured":"Im, S., Kell, N., Kulkarni, J., Panigrahi, D.: Tight bounds for online vector scheduling. SIAM J. Comput. 48(1), 93\u2013121 (2019). https:\/\/doi.org\/10.1137\/17M111835X","journal-title":"SIAM J. Comput."},{"key":"2132_CR36","doi-asserted-by":"publisher","unstructured":"Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of SODA, pp. 1405\u20131424 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.93","DOI":"10.1137\/1.9781611973730.93"},{"issue":"4","key":"2132_CR37","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014). https:\/\/doi.org\/10.1287\/opre.2014.1289","journal-title":"Oper. Res."},{"issue":"4","key":"2132_CR38","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1287\/moor.2016.0782","volume":"41","author":"A Gupta","year":"2016","unstructured":"Gupta, A., Molinaro, M.: How the experts algorithm can help solve lps online. Math. Oper. Res. 41(4), 1404\u20131431 (2016). https:\/\/doi.org\/10.1287\/moor.2016.0782","journal-title":"Math. Oper. Res."},{"key":"2132_CR39","doi-asserted-by":"publisher","unstructured":"Kesselheim, T., Molinaro, M., Singla, S.: Online and bandit algorithms beyond $${\\mathcalligra{l}}_{\\text{p}}$$ norms. In: Proceedings of SODA, pp. 1566\u20131593 (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch58","DOI":"10.1137\/1.9781611977554.ch58"},{"key":"2132_CR40","doi-asserted-by":"publisher","unstructured":"Hajiaghayi, M.T., Kim, J.H., Leighton, T., R\u00e4cke, H.: Oblivious routing in directed graphs with random demands. In: Proceedings of STOC, pp. 193\u2013201 (2005). https:\/\/doi.org\/10.1145\/1060590.1060619","DOI":"10.1145\/1060590.1060619"},{"issue":"4","key":"2132_CR41","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987). https:\/\/doi.org\/10.1007\/BF02579324","journal-title":"Combinatorica"},{"key":"2132_CR42","doi-asserted-by":"publisher","unstructured":"Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: Proceedings of STOC, pp. 165\u2013178 (2007). https:\/\/doi.org\/10.1145\/1250790.1250816","DOI":"10.1145\/1250790.1250816"},{"key":"2132_CR43","doi-asserted-by":"publisher","unstructured":"Leonardi, S.: On-line network routing. In: Online Algorithms. LNCS, vol. 1442, pp. 242\u2013267 (1996). https:\/\/doi.org\/10.1007\/BFb0029572","DOI":"10.1007\/BFb0029572"},{"key":"2132_CR44","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"issue":"297","key":"2132_CR45","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/01621459.1962.10482149","volume":"57","author":"G Bennett","year":"1962","unstructured":"Bennett, G.: Probability inequalities for the sum of independent random variables. JASA 57(297), 33\u201345 (1962). https:\/\/doi.org\/10.1080\/01621459.1962.10482149","journal-title":"JASA"},{"key":"2132_CR46","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02132-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02132-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02132-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T15:53:40Z","timestamp":1740758020000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02132-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,8]]},"references-count":46,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2132"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02132-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,8]]},"assertion":[{"value":"28 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}