{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T22:44:37Z","timestamp":1781649877392,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong General Research Fund","award":["16202619"],"award-info":[{"award-number":["16202619"]}]},{"name":"National Science Foundation","award":["AitF-1637598, CNS-1518941, CNS-1908298"],"award-info":[{"award-number":["AitF-1637598, CNS-1518941, CNS-1908298"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"<jats:p>We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging.<\/jats:p>","DOI":"10.1145\/3428336","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T19:54:15Z","timestamp":1606766055000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging"],"prefix":"10.1145","volume":"4","author":[{"given":"Bo","family":"Sun","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"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":"Tongxin","family":"Li","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Hajiesmaili","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny H.K.","family":"Tsang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jacob D Abernethy Elad Hazan and Alexander Rakhlin. 2009. Competing in the dark: An efficient algorithm for bandit linear optimization. (2009)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2011.07.015"},{"key":"e_1_2_1_3_1","volume-title":"2012 IEEE Fifth International Conference on Cloud Computing. IEEE, 188--195","author":"Adnan Muhammad Abdullah","year":"2012","unstructured":"Muhammad Abdullah Adnan, Ryo Sugihara, and Rajesh K Gupta. 2012. Energy efficient geographical load balancing via dynamic deferral of workload. In 2012 IEEE Fifth International Conference on Cloud Computing. IEEE, 188--195."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2014.1289"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2018.2887194"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSUSC.2020.2979854"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS.2018.8624184"},{"key":"e_1_2_1_8_1","volume-title":"Convex optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. 2004. Convex optimization .Cambridge university press."},{"key":"e_1_2_1_9_1","volume-title":"The design of competitive online algorithms via a primal-dual approach","author":"Buchbinder Niv","unstructured":"Niv Buchbinder and Joseph Naor. 2009a. The design of competitive online algorithms via a primal-dual approach .Now Publishers Inc."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0363"},{"key":"e_1_2_1_11_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_12_1","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1109\/TSP.2011.2169407","article-title":"Convergence analysis of saddle point problems in time varying wireless systems?Control theoretical approach","volume":"60","author":"Chen Junting","year":"2011","unstructured":"Junting Chen and Vincent KN Lau. 2011. Convergence analysis of saddle point problems in time varying wireless systems?Control theoretical approach. IEEE Transactions on Signal Processing , Vol. 60, 1 (2011), 443--452.","journal-title":"IEEE Transactions on Signal Processing"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.034"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing","author":"Nikhil","unstructured":"Nikhil R. Devanur and Kamal Jain. 2012. Online Matching with Concave Returns. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (New York, New York, USA) (STOC '12). Association for Computing Machinery, New York, NY, USA, 137--144."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0003-0"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9239-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103448"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/PESGM.2017.8274166"},{"key":"e_1_2_1_19_1","volume-title":"Proc. of ACM eEnergy. 303--314","author":"Gupta Vani","year":"2019","unstructured":"Vani Gupta, Prashant Shenoy, and Ramesh K Sitaraman. 2019. Combining Renewable Solar and Open Air Cooling for Greening Internet-Scale Distributed Networks. In Proc. of ACM eEnergy. 303--314."},{"key":"e_1_2_1_20_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_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112004"},{"key":"e_1_2_1_22_1","volume-title":"Multiple Knapsack Problems","author":"Kellerer Hans","unstructured":"Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Multiple Knapsack Problems .Springer Berlin Heidelberg, Berlin, Heidelberg, 285--316."},{"key":"e_1_2_1_23_1","volume-title":"Proc. of ACM eEnergy .","author":"Lee Zachary","unstructured":"Zachary Lee, Tongxin Li, and S. H. Low. 2019. ACN-Data charging dataset: analysis and applications. In Proc. of ACM eEnergy ."},{"key":"e_1_2_1_24_1","volume-title":"2018 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm). IEEE, 1--7.","author":"Lee Zachary J","year":"2018","unstructured":"Zachary J Lee, Daniel Chang, Cheng Jin, George S Lee, Rand Lee, Ted Lee, and Steven H Low. 2018. Large-scale adaptive electric vehicle charging. In 2018 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm). IEEE, 1--7."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322205.3311081"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2308295"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486187"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0954"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1109\/TPDS.2013.69","article-title":"Temporal load balancing with service delay guarantees for data center energy cost optimization","volume":"25","author":"Luo Jianying","year":"2013","unstructured":"Jianying Luo, Lei Rao, and Xue Liu. 2013. Temporal load balancing with service delay guarantees for data center energy cost optimization. IEEE Transactions on Parallel and Distributed Systems , Vol. 25, 3 (2013), 775--784.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"e_1_2_1_30_1","volume-title":"Inequalities involving functions and their integrals and derivatives","author":"Mitrinovic Dragoslav S","unstructured":"Dragoslav S Mitrinovic, Josip Pecaric, and Arlington M Fink. 1991. Inequalities involving functions and their integrals and derivatives. Vol. 53. Springer Science & Business Media."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPAN.2005.19"},{"key":"e_1_2_1_32_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_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.03.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2018.2851375"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592584"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2018.03.034"},{"key":"e_1_2_1_37_1","volume-title":"BOLA: Near-Optimal Bitrate Adaptation for Online Videos","author":"Spiteri Kevin","year":"2020","unstructured":"Kevin Spiteri, Rahul Urgaonkar, and Ramesh K Sitaraman. 2020. BOLA: Near-Optimal Bitrate Adaptation for Online Videos. IEEE\/ACM Transactions on Networking (2020)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396851.3397727"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2020.2971810"},{"key":"e_1_2_1_40_1","volume-title":"Mechanism Design for Online Resource Allocation: A Unified Approach. In Abstracts of the 2020 SIGMETRICS\/Performance Joint International Conference on Measurement and Modeling of Computer Systems","author":"Tan Xiaoqi","unstructured":"Xiaoqi Tan, Bo Sun, Alberto Leon-Garcia, Yuan Wu, and Danny H.K. Tsang. 2020. Mechanism Design for Online Resource Allocation: A Unified Approach. In Abstracts of the 2020 SIGMETRICS\/Performance Joint International Conference on Measurement and Modeling of Computer Systems (Boston, MA, USA) (SIGMETRICS '20). Association for Computing Machinery, New York, NY, USA, 11--12."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/LANMAN.2019.8847134"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.01.031"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379482"},{"key":"e_1_2_1_44_1","volume-title":"Online Linear Programming with Uncertain Constraints. In 2019 53rd Annual Conference on Information Sciences and Systems (CISS). IEEE, 1--6.","author":"Yang Lin","year":"2019","unstructured":"Lin Yang, Mohammad H Hajiesmaili, and Wing S Wong. 2019. Online Linear Programming with Uncertain Constraints. In 2019 53rd Annual Conference on Information Sciences and Systems (CISS). IEEE, 1--6."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084460"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 5th international conference on Future energy systems . 253--263","author":"Zheng Zizhan","year":"2014","unstructured":"Zizhan Zheng and Ness Shroff. 2014. Online welfare maximization for electric vehicle charging with electricity cost. In Proceedings of the 5th international conference on Future energy systems . 253--263."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524430"},{"key":"e_1_2_1_48_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\/3428336","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:58Z","timestamp":1750197778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3428336"],"URL":"https:\/\/doi.org\/10.1145\/3428336","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"2020-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}