论文标题
改进了在随机订单模型中的背包和差距的在线算法
Improved Online Algorithms for Knapsack and GAP in the Random Order Model
论文作者
论文摘要
背包问题是组合优化的经典问题之一：给定一组项目，每个项目的大小和利润指定，目标是将最大的利润包装在有限容量的背包中。在在线设置中，项目将一一揭示，如果当前项目被包装或永远丢弃，则必须在抵达时立即且不可撤销地完成。我们在随机阶模型中研究在线变体，其中输入序列是项目集的均匀随机排列。 我们为此问题开发了一种随机（1/6.65） - 竞争算法，表现优于竞争比1/8.06的当前最佳算法[Kesselheim等。 Siam J. Comp。 47（5）]。我们的算法基于两个新的见解：我们引入了一种新型算法方法，该方法采用了两种给定的算法，对受限制的项目类优化，依次根据输入序列进行了优化。此外，我们研究并利用了背包问题与两个秘书问题的关系。 广义分配问题（GAP）除了背包问题外还包括与调度和匹配有关的几个重要问题。我们表明，在同一在线设置中，应用所提出的顺序方法产生A（1/6.99）竞争性的随机算法的GAP。同样，我们提出的算法的表现优于竞争比1/8.06的当前最佳结果[Kesselheim等。 Siam J. Comp。 47（5）]。
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].
