论文标题
出发的在线背包问题
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 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 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.
