research-article

Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging

Authors:

Mohammad Hajiesmaili,

Danny H.K. TsangAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 4, Issue 3

Article No.: 51, Pages 1 - 32

https://doi.org/10.1145/3428336

Published: 30 November 2020 Publication History

Abstract

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.

References

[1]

Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. 2009. Competing in the dark: An efficient algorithm for bandit linear optimization. (2009).

[2]

Micah Adler, Ramesh K Sitaraman, and Harish Venkataramani. 2011. Algorithms for optimizing the bandwidth cost of content delivery. Computer Networks, Vol. 55, 18 (2011), 4007--4020.

[3]

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.

Digital Library

[4]

Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. 2014. A dynamic near-optimal algorithm for online linear programming. Operations Research, Vol. 62, 4 (2014), 876--890.

Digital Library

[5]

Bahram Alinia, Mohammad H Hajiesmaili, and Noël Crespi. 2019. Online EV charging scheduling with on-arrival commitment. IEEE Transactions on Intelligent Transportation Systems, Vol. 20, 12 (2019), 4524--4537.

Digital Library

[6]

Bahram Alinia, Mohammad H Hajiesmaili, Zachary J Lee, Noel Crespi, and Enrique Mallada. 2020. Online EV scheduling algorithms for adaptive charging networks with global peak constraints. IEEE Transactions on Sustainable Computing (2020).

[7]

Bahram Alinia, Mohammad Sadegh Talebi, Mohammad H Hajiesmaili, Ali Yekkehkhany, and Noel Crespi. 2018. Competitive online scheduling algorithms with applications in deadline-constrained EV charging. In 2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS). IEEE, 1--10.

[8]

Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. 2004. Convex optimization .Cambridge university press.

Digital Library

[9]

Niv Buchbinder and Joseph Naor. 2009a. The design of competitive online algorithms via a primal-dual approach .Now Publishers Inc.

Digital Library

[10]

Niv Buchbinder and Joseph Naor. 2009b. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, Vol. 34, 2 (2009), 270--286.

Digital Library

[11]

Deeparnab Chakrabarty, Yunhong Zhou, and Rajan Lukose. 2008. Online knapsack problems. In Workshop on internet and network economics (WINE) .

[12]

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.

Digital Library

[13]

Francis YL Chin, Bin Fu, Jiuling Guo, Shuguang Han, Jueliang Hu, Minghui Jiang, Guohui Lin, Hing-Fung Ting, Luping Zhang, Yong Zhang, et almbox. 2015. Competitive algorithms for unbounded one-way trading. Theoretical Computer Science, Vol. 607 (2015), 35--48.

Digital Library

[14]

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.

[15]

Ran El-Yaniv, Amos Fiat, Richard M Karp, and Gordon Turpin. 2001. Optimal search and one-way trading online algorithms. Algorithmica, Vol. 30, 1 (2001), 101--139.

[16]

Hiroshi Fujiwara, Kazuo Iwama, and Yoshiyuki Sekiguchi. 2011. Average-case competitive analyses for one-way trading. Journal of Combinatorial Optimization, Vol. 21, 1 (2011), 83--107.

Digital Library

[17]

Edward F Grove. 1991. The harmonic online k-server algorithm is competitive. In Proceedings of the twenty-third annual ACM symposium on Theory of computing. 260--266.

Digital Library

[18]

Linqi Guo, Karl F Erliksson, and Steven H Low. 2017. Optimal online adaptive electric vehicle charging. In 2017 IEEE Power & Energy Society General Meeting. IEEE, 1--5.

[19]

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.

Digital Library

[20]

Kazuo Iwama and Shiro Taketomi. 2002. Removable online knapsack problems. In International Colloquium on Automata, Languages, and Programming. Springer, 293--305.

[21]

G Stephen Jones. 1964. Fundamental inequalities for discrete and discontinuous functional equations. J. Soc. Indust. Appl. Math., Vol. 12, 1 (1964), 43--57.

[22]

Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Multiple Knapsack Problems .Springer Berlin Heidelberg, Berlin, Heidelberg, 285--316.

[23]

Zachary Lee, Tongxin Li, and S. H. Low. 2019. ACN-Data charging dataset: analysis and applications. In Proc. of ACM eEnergy .

[24]

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.

[25]

Qiulin Lin, Hanling Yi, John Pang, Minghua Chen, Adam Wierman, Michael Honig, and Yuanzhang Xiao. 2019. Competitive online optimization under inventory constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 3, 1 (2019), 1--28.

Digital Library

[26]

Zhenhua Liu, Minghong Lin, Adam Wierman, Steven Low, and Lachlan LH Andrew. 2014. Greening geographical load balancing. IEEE/ACM Transactions on Networking, Vol. 23, 2 (2014), 657--671.

Digital Library

[27]

Brendan Lucier, Ishai Menache, Joseph Naor, and Jonathan Yaniv. 2013. Efficient online scheduling for deadline-sensitive jobs. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures . 305--314.

Digital Library

[28]

George S Lueker. 1998. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, Vol. 29, 2 (1998), 277--305.

Digital Library

[29]

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.

[30]

Dragoslav S Mitrinovic, Josip Pecaric, and Arlington M Fink. 1991. Inequalities involving functions and their integrals and derivatives. Vol. 53. Springer Science & Business Media.

[31]

John Noga and Veerawan Sarbua. 2005. An online partially fractional knapsack problem. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'05). IEEE, 5--pp.

Digital Library

[32]

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.

[33]

David Pisinger. 2005. Where are the hard knapsack problems? Computers & Operations Research, Vol. 32, 9 (2005), 2271--2284.

Digital Library

[34]

Guannan Qu and Na Li. 2018. On the exponential stability of primal-dual gradient dynamics. IEEE Control Systems Letters, Vol. 3, 1 (2018), 43--48.

[35]

Asfandyar Qureshi, Rick Weber, Hari Balakrishnan, John Guttag, and Bruce Maggs. 2009. Cutting the electric bill for internet-scale systems. In Proceedings of the ACM SIGCOMM 2009 conference on Data communication. 123--134.

Digital Library

[36]

Pascal Schroeder, Robert Dochow, and Günter Schmidt. 2018. Optimal solutions for the online time series search and one-way trading problem with interrelated prices and a profit function. Computers & Industrial Engineering, Vol. 119 (2018), 465--471.

[37]

Kevin Spiteri, Rahul Urgaonkar, and Ramesh K Sitaraman. 2020. BOLA: Near-Optimal Bitrate Adaptation for Online Videos. IEEE/ACM Transactions on Networking (2020).

[38]

Bo Sun, Tongxin Li, Steven H Low, and Danny HK Tsang. 2020. ORC: An Online Competitive Algorithm for Recommendation and Charging Schedule in Electric Vehicle Charging Network. In Proceedings of the Eleventh ACM International Conference on Future Energy Systems. 144--155.

Digital Library

[39]

X. Tan, A. Leon-Garcia, Y. Wu, and D. H. K. Tsang. 2020. Online Combinatorial Auctions for Resource Allocation With Supply Costs and Capacity Limits. IEEE Journal on Selected Areas in Communications, Vol. 38, 4 (2020), 655--668.

[40]

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.

[41]

Cong Wang and Michael Zink. 2019. Sustainable Cloud Encoding for Adaptive Bitrate Streaming over CDNs. In 2019 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN) . 1--6.

[42]

Wei Wang, Liying Wang, Yingjie Lan, and Jean X Zhang. 2016. Competitive difference analysis of the one-way trading problem with limited information. European Journal of Operational Research, Vol. 252, 3 (2016), 879--887.

[43]

Lin Yang, Mohammad H Hajiesmaili, Ramesh Sitaraman, Adam Wierman, Enrique Mallada, and Wing S Wong. 2020. Online Linear Optimization with Inventory Management Constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4, 1 (2020), 1--29.

Digital Library

[44]

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.

[45]

Zijun Zhang, Zongpeng Li, and Chuan Wu. 2017. Optimal Posted Prices for Online Cloud Resource Allocation. Proc. ACM Meas. Anal. Comput. Syst., Vol. 1, 1 (June 2017), bibinfonumpages26 pages.

Digital Library

[46]

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.

Digital Library

[47]

Zizhan Zheng and Ness B Shroff. 2016. Online multi-resource allocation for deadline sensitive jobs with partial values in the cloud. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. IEEE, 1--9.

Digital Library

[48]

Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. 2008. Budget constrained bidding in keyword auctions and online knapsack problems. In International Workshop on Internet and Network Economics. Springer, 566--576.

Digital Library

Cited By

Sun BHuang JChristianson NHajiesmaili MWierman ABoutaba RSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Online algorithms with uncertainty-quantified predictionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693985(47056-47077)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693985
Lechowicz AChristianson NSun BBashir NHajiesmaili MWierman AShenoy PSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Chasing convex functions with long-term constraintsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693120(26259-26289)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693120
Ting LWang HJhang JChuang K(2024)Online Spatial-Temporal EV Charging Scheduling with Incentive PromotionACM Transactions on Intelligent Systems and Technology10.1145/367818015:5(1-26)Online publication date: 17-Jul-2024
https://dl.acm.org/doi/10.1145/3678180
Show More Cited By

Index Terms

Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging

Recommendations

Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging
SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

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 ...
Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging
SIGMETRICS '21

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 ...
Online welfare maximization for electric vehicle charging with electricity cost
e-Energy '14: Proceedings of the 5th international conference on Future energy systems

The accelerated adoption of EVs in the last few years has raised concerns that the power grid can get overloaded when a large number of EVs are charged simultaneously. A promising direction is to implement large scale automated scheduling of EV charging ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 4, Issue 3

POMACS

December 2020

345 pages

EISSN:2476-1249

DOI:10.1145/3440131

Editors:
Augustin Chaintreau
Columbia University
,
Leana Golubchik
University of Southern California
,
Zhi-Li Zhang
University of Minnesota

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 November 2020

Published in POMACS Volume 4, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Hong Kong General Research Fund
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
822
Total Downloads

Downloads (Last 12 months)137
Downloads (Last 6 weeks)19

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sun BHuang JChristianson NHajiesmaili MWierman ABoutaba RSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Online algorithms with uncertainty-quantified predictionsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693985(47056-47077)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693985
Lechowicz AChristianson NSun BBashir NHajiesmaili MWierman AShenoy PSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Chasing convex functions with long-term constraintsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693120(26259-26289)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693120
Ting LWang HJhang JChuang K(2024)Online Spatial-Temporal EV Charging Scheduling with Incentive PromotionACM Transactions on Intelligent Systems and Technology10.1145/367818015:5(1-26)Online publication date: 17-Jul-2024
https://dl.acm.org/doi/10.1145/3678180
Bostandoost RLechowicz AHanafy WBashir NShenoy PHajiesmaili M(2024)LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain DemandProceedings of the 15th ACM International Conference on Future and Sustainable Energy Systems10.1145/3632775.3661942(27-45)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3632775.3661942
Lin QSu JChen M(2024)Competitive Online Age-of-Information Optimization for Energy Harvesting SystemsIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621320(901-910)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621320
Leng SGuo YZhang LHao FCao XLi FKou W(2024)Online and Collaboratively Mitigating Multi-Vector DDoS Attacks for Cloud-Edge ComputingICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10623052(1394-1399)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10623052
Zhang WHu H(2024)Designing of data-driven strategies for the online one-way trading problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.124843256:COnline publication date: 5-Dec-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.124843
Bai MCardonha C(2023)Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear UtilitiesSSRN Electronic Journal10.2139/ssrn.4350988Online publication date: 2023
https://doi.org/10.2139/ssrn.4350988
Lechowicz AChristianson NZuo JBashir NHajiesmaili MWierman AShenoy P(2023)The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load ShiftingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36267767:3(1-32)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626776
Zhu GZhao DTian KZhang ZYuan RMa H(2023)Combining Smart Speaker and Smart Meter to Infer Your Residential Power Usage by Self-supervised Cross-modal LearningProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/36109057:3(1-26)Online publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1145/3610905
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents