Generalized assignment and knapsack problems in the random-order model

• 成果类型: Article; Early Access
• 署名作者: Klimm, Max; Knaack, Martin
• 署名单位: Technical University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02405-6
• 发表日期: 2026-08-12
• 关键词: Generalized assignment problem; knapsack problem; online optimization; Competitive analysis; Random-order model; algorithms

摘要

We study different online optimization problems in the random-order model. There is a finite set of bins with known capacities and a finite set of items arriving in uniform random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or whether the item is rejected. In this setting, an algorithm is alpha -competitive if the total expected value of all items assigned to the bins is at least an alpha -fraction of the total value of an optimal assignment that knows all items beforehand. We give an algorithm that is alpha -competitive with alpha=(1-ln2)/2 approximate to 1/6.52 improving upon the previous best algorithm with alpha approximate to 1/6.99 for the generalized assignment problem and the previous best algorithm with alpha approximate to 1/6.65 for the integral knapsack problem. We then study the fractional knapsack problem where we have a single bin and it is also allowed to pack items fractionally. For that case, we obtain an algorithm that is alpha -competitive with alpha=1/e approximate to 1/2.71 improving on the previous best algorithm with alpha=1/4.39 . We further show that the competitive ratio of 1/e is best-possible for randomized algorithms in this model.