A Caltech Library Service

Data-driven Competitive Algorithms for Online Knapsack and Set Cover

Zeynali, Ali and Sun, Bo and Hajiesmaili, Mohammad and Wierman, Adam (2021) Data-driven Competitive Algorithms for Online Knapsack and Set Cover. In: Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21). Association for the Advancement of Artificial Intelligence , Palo Alto, CA, pp. 10833-10841.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Hajiesmaili, Mohammad0000-0001-9278-2254
Additional Information:© 2021 Association for the Advancement of Artificial Intelligence. Published 2021-05-18. Ali Zeynali and Mohammad Hajiesmaili acknowledge the support from NSF grant CNS-1908298, and NSF CAREER 2045641. Adam Wierman’s research is supported by NSF AitF-1637598, and CNS-1518941. Also, Bo Sun received the support from Hong Kong General Research Fund, GRF 16211220.
Funding AgencyGrant Number
Hong Kong Research Grant Council16211220
Subject Keywords:Online Learning & Bandits, Other Applications, Optimization
Record Number:CaltechAUTHORS:20210510-092934731
Persistent URL:
Official Citation:Zeynali, A., Sun, B., Hajiesmaili, M., & Wierman, A. (2021). Data-driven Competitive Algorithms for Online Knapsack and Set Cover. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10833-10841
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109026
Deposited By: Tony Diaz
Deposited On:10 May 2021 17:49
Last Modified:28 Sep 2021 16:18

Repository Staff Only: item control page