{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:19Z","timestamp":1784110339703,"version":"3.55.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,12,14]],"date-time":"2021-12-14T00:00:00Z","timestamp":1639440000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2021,12,14]]},"abstract":"<jats:p>In this paper, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of O(\u03b8\u03b1 ) and O(\u0142og\u0142(\u03b8\u03b1)), respectively, where \u03b1 is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and \u03b8 is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.<\/jats:p>","DOI":"10.1145\/3491042","type":"journal-article","created":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T18:32:19Z","timestamp":1639593139000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Competitive Algorithms for Online Multidimensional Knapsack Problems"],"prefix":"10.1145","volume":"5","author":[{"given":"Lin","family":"Yang","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst, Amherst , MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Zeynali","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad H.","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ramesh K.","family":"Sitaraman","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst &amp; Akamai Technologies, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2018.2887194"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSUSC.2020.2979854"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS.2018.8624184"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0965-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.24"},{"key":"e_1_2_1_6_1","volume-title":"Proc. ACM Meas. Anal. Comput. Syst.","volume":"5","author":"Balogh J\u00e1nos","year":"2021","unstructured":"J\u00e1nos Balogh, J\u00f3zsef B\u00e9k\u00e9si, Gy\u00f6rgy D\u00f3sa, Leah Epstein, and Asaf Levin. 2021. A new lower bound for classic online bin packing. Algorithmica (2021), 1--16. Proc. ACM Meas. Anal. Comput. Syst., Vol. 5, No. 3, Article 30. Publication date: December 2021. 30:22 Lin Yang et al."},{"key":"e_1_2_1_7_1","volume-title":"The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. arXiv preprint arXiv:2011.10124","author":"Balseiro Santiago","year":"2020","unstructured":"Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2020. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. arXiv preprint arXiv:2011.10124 (2020)."},{"key":"e_1_2_1_8_1","volume-title":"Online computation and competitive analysis","author":"Borodin Allan","unstructured":"Allan Borodin and Ran El-Yaniv. 2005. Online computation and competitive analysis. Cambridge University Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.08.007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/766502.766506"},{"key":"e_1_2_1_11_1","volume-title":"The design of competitive online algorithms via a primal-dual approach","author":"Buchbinder Niv","unstructured":"Niv Buchbinder and Joseph Naor. 2009. The design of competitive online algorithms via a primal-dual approach. Now Publishers Inc."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC42340.2020.9303856"},{"key":"e_1_2_1_15_1","volume-title":"Workshop on internet and network economics (WINE).","author":"Chakrabarty Deeparnab","year":"2008","unstructured":"Deeparnab Chakrabarty, Yunhong Zhou, and Rajan Lukose. 2008. Online knapsack problems. In Workshop on internet and network economics (WINE)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314555"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007383"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.034"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2016.12.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9566-4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-3448-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377--2217(03)00274--1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.32"},{"key":"e_1_2_1_25_1","unstructured":"Rainer Gawlick Anil Kamath Serge Plotkin and KG Ramakrishnan. 1995. Routing and Admission Control of Virtual Circuits in General Topology Networks. (1995)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-019-00728-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2017.09.002"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.009"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601796"},{"key":"e_1_2_1_30_1","volume-title":"Optimal admission control policy for mobile cloud computing hotspot with cloudlet. In 2012 IEEE wireless communications and networking conference (WCNC)","author":"Hoang Dinh Thai","unstructured":"Dinh Thai Hoang, Dusit Niyato, and Ping Wang. 2012. Optimal admission control policy for mobile cloud computing hotspot with cloudlet. In 2012 IEEE wireless communications and networking conference (WCNC). IEEE, 3145--3149."},{"key":"e_1_2_1_31_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Iwama Kazuo","unstructured":"Kazuo Iwama and Shiro Taketomi. 2002. Removable online knapsack problems. In International Colloquium on Automata, Languages, and Programming. Springer, 293--305."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447555.3464860"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOMS.2016.7502884"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486187"},{"key":"e_1_2_1_36_1","volume-title":"International Conference on Machine Learning. PMLR, 3296--3305","author":"Lykouris Thodoris","year":"2018","unstructured":"Thodoris Lykouris and Sergei Vassilvtiskii. 2018. Competitive caching with machine learned advice. In International Conference on Machine Learning. PMLR, 3296--3305."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_2_1_38_1","volume-title":"NOMS 2016 - 2016 IEEE\/IFIP Network Operations and Management Symposium. 1003--1004","author":"Paris S.","unstructured":"S. Paris, J. Leguay, L. Maggi, M. Draief, and S. Chouvardas. 2016. Online experts for admission control in SDN. In NOMS 2016 - 2016 IEEE\/IFIP Network Operations and Management Symposium. 1003--1004."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0344"},{"key":"e_1_2_1_40_1","volume-title":"Improving online algorithms via ML predictions. Advances in Neural Information Processing Systems (NeurIPS 31","author":"Purohit Manish","year":"2018","unstructured":"Manish Purohit, Zoya Svitkina, and Ravi Kumar. 2018. Improving online algorithms via ML predictions. Advances in Neural Information Processing Systems (NeurIPS 31 (2018), 9661--9670."},{"key":"e_1_2_1_41_1","volume-title":"Pareto-Optimal LearningAugmented Algorithms for Online Conversion Problems. Advances in Neural Information Processing Systems (NeurIPS)","author":"Sun Bo","year":"2021","unstructured":"Bo Sun, Russell Lee, Mohammad H. Hajiesmaili, Adam Wierman, and Danny Tsang. 2021. Pareto-Optimal LearningAugmented Algorithms for Online Conversion Problems. Advances in Neural Information Processing Systems (NeurIPS) (2021)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396851.3397727"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428336"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392142"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2016.04.020"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2019.2918524"},{"key":"e_1_2_1_47_1","first-page":"37","article-title":"Overview of the algorithms for solving the multidimensional knapsack problems","volume":"4","author":"Varnamkhasti M Jalali","year":"2012","unstructured":"M Jalali Varnamkhasti. 2012. Overview of the algorithms for solving the multidimensional knapsack problems. Advanced Studies in Biology 4, 1 (2012), 37--47.","journal-title":"Advanced Studies in Biology"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133871"},{"key":"e_1_2_1_49_1","volume-title":"An Improved Weight-coded Evolutionary Algorithm for the Multidimensional Knapsack Problem. arXiv preprint arXiv:1302.5374","author":"Yuan Quan","year":"2013","unstructured":"Quan Yuan and Zhixin Yang. 2013. An Improved Weight-coded Evolutionary Algorithm for the Multidimensional Knapsack Problem. arXiv preprint arXiv:1302.5374 (2013)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17294"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745855"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084460"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524430"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_63"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491042","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:25:06Z","timestamp":1750195506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,14]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,12,14]]}},"alternative-id":["10.1145\/3491042"],"URL":"https:\/\/doi.org\/10.1145\/3491042","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,14]]},"assertion":[{"value":"2021-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}