The Online Knapsack Problem with Departures

Creators: Sun, Bo; Yang, Lin; Hajiesmaili, Mohammad; Wierman, Adam¹; Lui, John C. S.; Towsley, Don; Tsang, Danny H. K.

1. California Institute of Technology

Abstract

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 optimized algorithms, we also propose a data-driven online algorithm that can achieve near-optimal average performance under typical instances while guaranteeing the worst-case performance.

Copyright and License

Acknowledgement

Danny H.K. Tsang acknowledges the support received from the Hong Kong Research Grant Council (RGC) General Research Fund (Project 16202619 and Project 16211220) and Guangdong Research Project under Grant 2021JC02X149. 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, NGSDI2105494, and CAREER-2045641). The work of John C.S. Lui is supported in part by the RGC's SRFS2122-4S02. Don Towsley acknowledges the support received from Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196 (IoBT CRA).

Files

3578338.3593576.pdf

Files (29.4 MB)

Name	Size	Download all
3578338.3593576.pdf md5:6789888b77de7fdf7cb9dda41e5b501b	918.5 kB	Preview Download
SIGMETRICS23-sigmA388.mp4 md5:1c6b0bfd78e459dfcbdc0e8f3f83adf8	28.5 MB	Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes