{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:53:52Z","timestamp":1742936032582,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031327254"},{"type":"electronic","value":"9783031327261"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-32726-1_10","type":"book-chapter","created":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:28:43Z","timestamp":1684700923000},"page":"127-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Configuration Balancing for\u00a0Stochastic Requests"],"prefix":"10.1007","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":[]},{"given":"Rudy","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of SODA, pp. 1405\u20131424 (2015)","DOI":"10.1137\/1.9781611973730.93"},{"issue":"4","key":"10_CR2","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)","journal-title":"Oper. Res."},{"issue":"3","key":"10_CR3","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)","journal-title":"J. ACM"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/BFb0029569","volume-title":"Online Algorithms","author":"Y Azar","year":"1998","unstructured":"Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 178\u2013195. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029569"},{"issue":"2","key":"10_CR5","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)","journal-title":"J. Algorithms"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. Roy. Stat. Soc. Ser. B. Methodol. 17, 173\u2013184; discussion, 194\u2013203 (1955)","DOI":"10.1111\/j.2517-6161.1955.tb00191.x"},{"issue":"1","key":"10_CR7","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)","journal-title":"J. Algorithms"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: Proceedings of SODA, pp. 1647\u20131665. SIAM (2011)","DOI":"10.1137\/1.9781611973082.127"},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/11538462_22","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Chekuri, C., P\u00e1l, M.: Sampling bounds for stochastic optimization. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX\/RANDOM -2005. LNCS, vol. 3624, pp. 257\u2013269. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11538462_22"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: Proceedings of STOC, pp. 165\u2013178. ACM (2007)","DOI":"10.1145\/1250790.1250816"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","volume":"1","author":"GB Dantzig","year":"1955","unstructured":"Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1, 197\u2013206 (1955)","journal-title":"Manag. Sci."},{"issue":"4","key":"10_CR12","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)","journal-title":"Math. Oper. Res."},{"issue":"8","key":"10_CR13","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)","journal-title":"Naval Res. Logist."},{"key":"10_CR14","unstructured":"Eberle, F., Gupta, A., Megow, N., Moseley, B., Zhou, R.: Configuration balancing for stochastic requests. CoRR, abs\/2208.13702 (2022)"},{"issue":"2","key":"10_CR15","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. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR16","doi-asserted-by":"crossref","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. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.48"},{"issue":"1","key":"10_CR17","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)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"10_CR18","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)","journal-title":"Math. Oper. Res."},{"key":"10_CR19","doi-asserted-by":"crossref","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)","DOI":"10.1137\/080732250"},{"key":"10_CR20","doi-asserted-by":"crossref","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. ACM (2005)","DOI":"10.1145\/1060590.1060619"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Ibrahimpur, S., Swamy, C.: Approximation algorithms for stochastic minimum-norm combinatorial optimization. In: Proceedings of FOCS, pp. 966\u2013977. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00094"},{"issue":"1","key":"10_CR22","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)","journal-title":"SIAM J. Comput."},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Im, S., Kell, N., Panigrahi, D., Shadloo, M.: Online load balancing on related machines. In: Proceedings of STOC, pp. 30\u201343. ACM (2018)","DOI":"10.1145\/3188745.3188966"},{"issue":"1","key":"10_CR24","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)","journal-title":"SIAM J. Comput."},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"Leighton, T., Rao, S., Srinivasan, A.: Multicommodity flow and circuit switching. In: HICSS (7), pp. 459\u2013465. IEEE Computer Society (1998)","DOI":"10.1109\/HICSS.1998.649241"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","DOI":"10.1007\/BF01585745"},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/BFb0029572","volume-title":"Online Algorithms","author":"S Leonardi","year":"1998","unstructured":"Leonardi, S.: On-line network routing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 242\u2013267. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029572"},{"issue":"3","key":"10_CR28","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)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"10_CR29","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)","journal-title":"J. ACM"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Molinaro, M.: Stochastic p load balancing and moment problems via the l-function method. In: Proceedings of SODA, pp. 343\u2013354. SIAM (2019)","DOI":"10.1137\/1.9781611975482.22"},{"issue":"4","key":"10_CR31","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)","journal-title":"Combinatorica"},{"key":"10_CR32","unstructured":"Sagnol, G., Schmidt, D., Waldschmidt, G.: Restricted adaptivity in stochastic scheduling. In: Proceedings of ESA. LIPIcs, vol. 204, pp. 79:1\u201379:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"10_CR33","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)","journal-title":"Math. Program."},{"issue":"4","key":"10_CR34","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)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-32726-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T20:42:43Z","timestamp":1729456963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-32726-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031327254","9783031327261"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-32726-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madison, WI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/optimization.discovery.wisc.edu\/ipco-2023-madison\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"119","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}