Running summarizing tools on a new article
Check the paper below, then start its synthesis.
The Online Knapsack Problem with Departures
Bo Sun (Chinese University of Hong Kong), Lin Yang (Nanjing University), Mohammad Hajiesmaili (University of Massachusetts Amherst), Adam Wierman (California Institute of Technology), John C. S. Lui (Chinese University of Hong Kong), Don Towsley (University of Massachusetts Amherst), Danny H. K. Tsang (Hong Kong University of Science and Technology, The Hong Kong University of Science and Technology (Guangzhou))
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.