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.
翻译:在线 knapsack 问题是网络和操作研究中典型的在线资源分配问题。 它的基本版本研究如何将不同大小和价值的在线抵达项目包装成一个容量有限的 knapsack 。 在本文中, 我们研究一个包含项目偏离的通用版本, 同时考虑多个 knapsack 和多维项大小 。 我们设计一个基于门槛的在线算法, 并证明算法可以达到最优竞争比率 。 除了最差的情况性能保障之外, 我们还力求在典型情况下实现接近最佳的平均性能 。 为了实现这一目标, 我们提出一个数据驱动的在线算法, 在政策级中学习, 保证最坏的性能。 在追踪驱动的实验中, 我们显示我们的数据驱动算法在应用在线 knapsack 来安排云计算工作时, 优于其他基准算法 。