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. . (Unpublished)

[img] PDF - Accepted Version
See Usage Policy.


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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
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
Record Number:CaltechAUTHORS:20230316-204008302
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:120095
Deposited By: George Porter
Deposited On:16 Mar 2023 22:13
Last Modified:16 Mar 2023 22:13

Repository Staff Only: item control page