{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T18:49:25Z","timestamp":1783968565413,"version":"3.55.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong Research Grant Council (RGC) General Research Fund","award":["Project 16202619, Project 16211220, SRFS2122-4S02"],"award-info":[{"award-number":["Project 16202619, Project 16211220, SRFS2122-4S02"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-2146814, CPS-2136197, CNS-2106403, NGSDI-210564, CNS-2106299, CNS-2102963, CPS-2136199, NGSDI-2105494, CAREER-2045641"],"award-info":[{"award-number":["CNS-2146814, CPS-2136197, CNS-2106403, NGSDI-210564, CNS-2106299, CNS-2102963, CPS-2136199, NGSDI-2105494, CAREER-2045641"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering\n            <jats:italic>multiple knapsacks<\/jats:italic>\n            and\n            <jats:italic>multi-dimensional item sizes.<\/jats:italic>\n            We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case performance guarantees, we also aim to achieve near-optimal average performance under typical instances. Towards this goal, we propose a data-driven online algorithm that learns within a policy-class that guarantees a worst-case performance bound. In trace-driven experiments, we show that our data-driven algorithm outperforms other benchmark algorithms in an application of online knapsack to job scheduling for cloud computing.\n          <\/jats:p>","DOI":"10.1145\/3570618","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T20:20:10Z","timestamp":1670530810000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["The Online Knapsack Problem with Departures"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3172-7811","authenticated-orcid":false,"given":"Bo","family":"Sun","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9056-0500","authenticated-orcid":false,"given":"Lin","family":"Yang","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-2254","authenticated-orcid":false,"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-0199","authenticated-orcid":false,"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7466-0384","authenticated-orcid":false,"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7808-7375","authenticated-orcid":false,"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0135-7098","authenticated-orcid":false,"given":"Danny H.K.","family":"Tsang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou) &amp; The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1289"},{"key":"e_1_2_1_2_1","series-title":"SIAM journal on computing","volume-title":"The nonstochastic multiarmed bandit problem","author":"Auer Peter","year":"2002","unstructured":"Peter Auer , Nicolo Cesa-Bianchi , Yoav Freund , and Robert E Schapire . 2002. The nonstochastic multiarmed bandit problem . SIAM journal on computing , Vol. 32 , 1 ( 2002 ), 48--77. Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 2002. The nonstochastic multiarmed bandit problem. SIAM journal on computing , Vol. 32, 1 (2002), 48--77."},{"key":"e_1_2_1_3_1","volume-title":"Data-driven algorithm design. arXiv preprint arXiv:2011.07177","author":"Balcan Maria-Florina","year":"2020","unstructured":"Maria-Florina Balcan . 2020. Data-driven algorithm design. arXiv preprint arXiv:2011.07177 ( 2020 ). Maria-Florina Balcan. 2020. Data-driven algorithm design. arXiv preprint arXiv:2011.07177 (2020)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00064"},{"key":"e_1_2_1_5_1","volume-title":"The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research","author":"Balseiro Santiago","year":"2021","unstructured":"Santiago Balseiro , Haihao Lu , and Vahab Mirrokni . 2021. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research ( 2021 ), forthcoming. Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. 2021. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research (2021), forthcoming."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_2_1_7_1","volume-title":"Joseph Seffi Naor, et al","author":"Buchbinder Niv","year":"2009","unstructured":"Niv Buchbinder , Joseph Seffi Naor, et al . 2009 . The design of competitive online algorithms via a primal--dual approach. Foundations and Trends\u00ae in Theoretical Computer Science , Vol. 3 , 2--3 (2009), 93--263. Niv Buchbinder, Joseph Seffi Naor, et al. 2009. The design of competitive online algorithms via a primal--dual approach. Foundations and Trends\u00ae in Theoretical Computer Science, Vol. 3, 2--3 (2009), 93--263."},{"key":"e_1_2_1_8_1","volume-title":"Prediction, learning, and games","author":"Cesa-Bianchi Nicolo","unstructured":"Nicolo Cesa-Bianchi and G\u00e1bor Lugosi . 2006. Prediction, learning, and games . Cambridge university press . Nicolo Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction, learning, and games. Cambridge university press."},{"key":"e_1_2_1_9_1","unstructured":"Vincent Cohen-Addad and Varun Kanade. 2017. Online optimization of smoothed piecewise constant functions. In Artificial Intelligence and Statistics. PMLR 412--420.  Vincent Cohen-Addad and Varun Kanade. 2017. Online optimization of smoothed piecewise constant functions. In Artificial Intelligence and Statistics. PMLR 412--420."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284177"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530893"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_2_1_15_1","volume-title":"2012 IEEE Power and Energy Society General Meeting. IEEE, 1--8.","author":"Gan Lingwen","year":"2012","unstructured":"Lingwen Gan , Ufuk Topcu , and Steven H Low . 2012 . Stochastic distributed protocol for electric vehicle charging with discrete charging rate . In 2012 IEEE Power and Energy Society General Meeting. IEEE, 1--8. Lingwen Gan, Ufuk Topcu, and Steven H Low. 2012. Stochastic distributed protocol for electric vehicle charging with discrete charging rate. In 2012 IEEE Power and Energy Society General Meeting. IEEE, 1--8."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13100241"},{"key":"e_1_2_1_17_1","volume-title":"WINE 2021, Potsdam, Germany, December 14--17, 2021, Proceedings","volume":"13112","author":"Goyal Vineet","year":"2021","unstructured":"Vineet Goyal , Garud Iyengar , and Rajan Udwani . 2021 . Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. In Web and Internet Economics - 17th International Conference , WINE 2021, Potsdam, Germany, December 14--17, 2021, Proceedings , Vol. 13112 . Springer, 543. Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2021. Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. In Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14--17, 2021, Proceedings, Vol. 13112. Springer, 543."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.03.003"},{"key":"e_1_2_1_19_1","volume-title":"Online Traffic Routing: Deterministic Limits and Data-driven Enhancements. arXiv preprint arXiv:2109.08706","author":"Jalota Devansh","year":"2021","unstructured":"Devansh Jalota , Dario Paccagnan , Maximilian Schiffer , and Marco Pavone . 2021. Online Traffic Routing: Deterministic Limits and Data-driven Enhancements. arXiv preprint arXiv:2109.08706 ( 2021 ). Devansh Jalota, Dario Paccagnan, Maximilian Schiffer, and Marco Pavone. 2021. Online Traffic Routing: Deterministic Limits and Data-driven Enhancements. arXiv preprint arXiv:2109.08706 (2021)."},{"key":"e_1_2_1_20_1","volume-title":"Knapsack Problems","author":"Kellerer Hans","unstructured":"Hans Kellerer , Ulrich Pferschy , and David Pisinger . 2004. Multiple knapsack problems . In Knapsack Problems . Springer , 285--316. Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Multiple knapsack problems. In Knapsack Problems. Springer, 285--316."},{"key":"e_1_2_1_21_1","volume-title":"Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research","author":"Li Xiaocheng","year":"2021","unstructured":"Xiaocheng Li and Yinyu Ye. 2021. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research ( 2021 ). Xiaocheng Li and Yinyu Ye. 2021. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research (2021)."},{"key":"e_1_2_1_22_1","first-page":"302","article-title":"Online Interval Scheduling","volume":"94","author":"Lipton Richard J","year":"1994","unstructured":"Richard J Lipton and Andrew Tomkins . 1994 . Online Interval Scheduling . In SODA , Vol. 94. 302 -- 311 . Richard J Lipton and Andrew Tomkins. 1994. Online Interval Scheduling. In SODA, Vol. 94. 302--311.","journal-title":"SODA"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585758"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391236"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057230"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2019.3364"},{"key":"e_1_2_1_27_1","volume-title":"Proc. ACM Meas. Anal. Comput. Syst.","volume":"4","author":"Sun Bo","year":"2020","unstructured":"Bo Sun , Ali Zeynali , Tongxin Li , Mohammad Hajiesmaili , Adam Wierman , and Danny H.K. Tsang . 2020. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging . Proc. ACM Meas. Anal. Comput. Syst. , Vol. 4 , 3, Article 51 ( Nov. 2020 ), 32 pages. Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny H.K. Tsang. 2020. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging. Proc. ACM Meas. Anal. Comput. Syst. , Vol. 4, 3, Article 51 (Nov. 2020), 32 pages."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3392142"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491042"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i12.17294"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745855"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084460"},{"key":"e_1_2_1_33_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\/3570618","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570618","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570618","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:17Z","timestamp":1750178777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3570618"],"URL":"https:\/\/doi.org\/10.1145\/3570618","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2022-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}