Albers Susanne, Khan Arindam, Ladewig Leon
Department of Computer Science, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany.
Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 560012 India.
Algorithmica. 2021;83(6):1750-1785. doi: 10.1007/s00453-021-00801-2. Epub 2021 Feb 17.
The 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. in SIAM J Comput 47(5):1939-1964, 2018). 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 (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. in SIAM J Comput 47(5):1939-1964, 2018).
给定一组物品，每个物品由其大小和利润指定，目标是在容量有限的背包中找到最大利润的装填方案。在在线设置中，物品逐个被揭示，并且关于当前物品是被装入背包还是永远丢弃的决策，必须在物品到达时立即且不可撤销地做出。我们研究随机顺序模型下的在线变体，其中输入序列是物品集的均匀随机排列。我们为这个问题开发了一种随机化的（1/6.65）竞争算法，其性能优于当前竞争比为1/8.06的最佳算法（Kesselheim等人，《SIAM 计算机学报》47(5):1939 - 1964，2018）。我们的算法基于两个新的见解：我们引入了一种新颖的算法方法，该方法在输入序列上依次使用针对受限物品类优化的两个给定算法。此外，我们研究并利用了背包问题与2 - 秘书问题的关系。广义分配问题（GAP）除了包含背包问题外，还包括几个与调度和匹配相关的重要问题。我们表明，在相同的在线设置下，应用所提出的顺序方法为GAP产生了一种（1/6.99）竞争的随机化算法。同样，我们提出的算法优于当前竞争比为1/8.06的最佳结果（Kesselheim等人，《SIAM 计算机学报》47(5):1939 - 1964，2018）。
