The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of 4.39. Our result significantly improves over the previously best known competitive ratio of 9.37 and surpasses the current best 6.65-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above.
翻译：分数背包问题是组合优化的经典问题之一,离线式环境对此非常了解。然而,迄今为止,相应的在线设置在计算机科学理论文献中只得到简单处理,尽管它出现在几个应用中。即使是以前最著名的竞争比率保障也比流行随机排序模式中最著名的整体问题更糟糕。我们显示,在线分数背包问题有一种算法,它承认了4.39的竞争性比率。我们的结果大大高于以前最著名的9.37的竞争性比率,超过了目前综合案件6.65的最好的竞争性算法。此外,我们的算法与实现上述结果的随机算法相比,具有确定性。
相关内容
微信扫码咨询专知VIP会员