The Online Knapsack Problem with Departures
The Online Knapsack Problem with Departures
复制标题
出发时的在线背包问题
DOI：
10.1145/3570618
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tsang, Danny H.K.
中科院分区：
文献类型：
--
作者：
Sun, Bo;Yang, Lin;Hajiesmaili, Mohammad;Wierman, Adam;Lui, John C.;Towsley, Don;Tsang, Danny H.K.
在线背包问题是网络和运筹学中的经典在线资源分配问题。它的基本版本研究如何将不同大小和价值的在线到达物品打包到容量有限的背包中。本文研究了一个包含项目偏离、同时包含多背包和多维项目大小的一般版本，设计了一个基于阈值的在线算法，并证明了该算法可以获得订单最优竞争比。除了最坏情况下的性能保证外，我们还旨在在典型情况下实现接近最佳的平均性能。为了实现这一目标，我们提出了一个数据驱动的在线算法，学习的政策类，保证最坏情况下的性能界限。在跟踪驱动的实验中，我们表明，我们的数据驱动算法优于其他基准算法的应用程序的在线背包作业调度云计算。
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 consideringmultiple knapsacksandmulti-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.