CaltechAUTHORS
Published June 2023 | Version Published
Conference Paper Open

The Online Knapsack Problem with Departures

Creators

  • 1. ROR icon 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

© 2023 Owner/Author.

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
md5:6789888b77de7fdf7cb9dda41e5b501b
918.5 kB Preview Download
md5:1c6b0bfd78e459dfcbdc0e8f3f83adf8
28.5 MB Preview Download

Additional details

Related works

Is variant form of
https://authors.library.caltech.edu/records/8zcg9-swy47 (URL)
https://authors.library.caltech.edu/records/p3hza-x2y93 (URL)

Funding

University Grants Committee
16202619
University Grants Committee
16211220
Guangdong Research Project
Grant 2021JC02X149
National Science Foundation
CNS-2146814
National Science Foundation
ECCS-2136197
National Science Foundation
CNS-2106403
National Science Foundation
CNS-210564
Amazon (United States)
National Science Foundation
CNS-2106299
National Science Foundation
CNS-2102963
National Science Foundation
ECCS-2136199
National Science Foundation
CNS-2105494
National Science Foundation
CNS-2045641
University Grants Committee
SRFS2122-4S02
DEVCOM Army Research Laboratory
W911NF-17-2-0196