A Caltech Library Service

The Online Knapsack Problem with Departures

Sun, Bo and Yang, Lin and Hajiesmaili, Mohammad and Wierman, Adam and Lui, John C. S. and Towsley, Don and Tsang, Danny H. K. (2022) The Online Knapsack Problem with Departures. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6 (3). pp. 1-32. ISSN 2476-1249. doi:10.1145/3570618.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 multiple knapsacks and multi-dimensional item sizes. 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.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemDiscussion Paper
Sun, Bo0000-0003-3172-7811
Yang, Lin0000-0001-9056-0500
Hajiesmaili, Mohammad0000-0001-9278-2254
Wierman, Adam0000-0002-5923-0199
Lui, John C. S.0000-0001-7466-0384
Towsley, Don0000-0002-7808-7375
Tsang, Danny H. K.0000-0003-0135-7098
Additional Information:© 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. Bo Sun and Danny H.K. Tsang acknowledge the support received from the Hong Kong Research Grant Council (RGC) General Research Fund (Project 16202619 and Project 16211220). Adam Wierman acknowledges the support received from NSF grants (CNS-2146814, CPS-2136197, CNS-2106403, and NGSDI-210564) and the additional support from Amazon AWS. Mohammad Hajiesmaili’s research is supported by NSF grants (CNS-2106299, CNS-2102963, CPS-2136199, NGSDI-2105494, and CAREER-2045641). The work of John C.S. Lui is supported in part by the RGC’s SRFS2122-4S02.
Funding AgencyGrant Number
Research Grants Council of Hong Kong16202619
Research Grants Council of Hong Kong16211220
Amazon Web ServicesUNSPECIFIED
Research Grants Council of Hong KongSRFS2122-4S02
Issue or Number:3
Record Number:CaltechAUTHORS:20230103-817548100.24
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118625
Deposited By: Research Services Depository
Deposited On:27 Jan 2023 19:08
Last Modified:16 Mar 2023 22:09

Repository Staff Only: item control page