CaltechAUTHORS
  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 (2020) Data-driven Competitive Algorithms for Online Knapsack and Set Cover. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210510-092934731

[img] PDF - Submitted Version
See Usage Policy.

442kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210510-092934731

Abstract

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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2012.05361arXivDiscussion Paper
ORCID:
AuthorORCID
Hajiesmaili, Mohammad0000-0001-9278-2254
Additional Information:Ali Zeynali and Mohammad Hajiesmaili acknowledge the support from NSF grant CNS-1908298. 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.
Funders:
Funding AgencyGrant Number
NSFCNS-1908298
NSFCCF-1637598
NSFCNS-1518941
Hong Kong Research Grant Council16211220
Record Number:CaltechAUTHORS:20210510-092934731
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210510-092934731
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109026
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:10 May 2021 17:49
Last Modified:10 May 2021 17:49

Repository Staff Only: item control page