The Online Knapsack Problem with Departures

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...

Full description

Saved in:
Bibliographic Details
Published in:Performance evaluation review 2023-06, Vol.51 (1), p.59-60
Main Authors: Sun, Bo, Yang, Lin, Hajiesmaili, Mohammad, Wierman, Adam, Lui, John C.S., Towsley, Don, Tsang, Danny H.K.
Format: Article
Language:English
Subjects:
Design and analysis of algorithms
Network algorithms
Network economics
Networks
Online algorithms
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0163-5999
1557-9484
DOI:10.1145/3606376.3593576