TY - GEN
T1 - Configuration Balancing for Stochastic Requests
AU - Eberle, Franziska
AU - Gupta, Anupam
AU - Megow, Nicole
AU - Moseley, Benjamin
AU - Zhou, Rudy
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple possible configurations, 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 makespan: 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 O(logmloglogm) -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 O(log m) 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 related machines to obtain a constant-factor approximation offline and an O(log log m) -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.
AB - The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple possible configurations, 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 makespan: 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 O(logmloglogm) -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 O(log m) 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 related machines to obtain a constant-factor approximation offline and an O(log log m) -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.
KW - load balancing
KW - stochastic routing
KW - stochastic scheduling
UR - http://www.scopus.com/inward/record.url?scp=85163395265&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85163395265&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-32726-1_10
DO - 10.1007/978-3-031-32726-1_10
M3 - Conference contribution
AN - SCOPUS:85163395265
SN - 9783031327254
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 141
BT - Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings
A2 - Del Pia, Alberto
A2 - Kaibel, Volker
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023
Y2 - 21 June 2023 through 23 June 2023
ER -