Abstract
Uncertainty in the input parameters is a major hurdle when trying to directly apply classical results from combinatorial optimization to real-word challenges. Hence, designing algorithms that handle incomplete knowledge provably well becomes a necessity. In view of the above, the author’s thesis [5] focuses on scheduling and packing problems under three models of uncertainty: stochastic, online, and dynamic. For this report, we highlight the results in online throughput maximization as well as dynamic multiple knapsack.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baruah, S.K., Haritsa, J.R., Sharma, N.: On-line scheduling to maximize task completions. In: RTSS, pp. 228–236. IEEE Computer Society (1994). https://doi.org/10.1109/REAL.1994.342713
Böhm, M., et al.: Fully dynamic algorithms for knapsack problems with polylogarithmic update time. CoRR, abs/2007.08415 (2020). https://arxiv.org/abs/2007.08415
Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005). https://doi.org/10.1137/S0097539700382820
Chen, L., Eberle, F., Megow, N., Schewior, K., Stein, C.: A general framework for handling commitment in online throughput maximization. Math. Prog. 183, 215–247 (2020). https://doi.org/10.1007/s10107-020-01469-2
Eberle, F.: Scheduling and packing under uncertainty. Ph.D. thesis, University of Bremen (2020). https://doi.org/10.26092/elib/436
Eberle, F., Megow, N., Schewior, K.: Optimally handling commitment issues in online throughput maximization. In: Proceedings of ESA 2020, pp. 41:1–41:15 (2020). https://doi.org/10.4230/LIPIcs.ESA.2020.41
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463–468 (1975). https://doi.org/10.1145/321906.321909
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Acknowledgments
I would like to thank my supervisor Nicole Megow for her continuous and excellent support and my colleagues and co-authors for many fruitful and inspiring discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Eberle, F. (2022). Scheduling and Packing Under Uncertainty. In: Trautmann, N., Gnägi, M. (eds) Operations Research Proceedings 2021. OR 2021. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-08623-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-08623-6_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-08622-9
Online ISBN: 978-3-031-08623-6
eBook Packages: Business and ManagementBusiness and Management (R0)