2020/12/01 by Susanne Albers, Arindam Khan, Albers, Susanne +3 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2012.00497
openalex publication_date 2020/12/01 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The knapsack problem is one of the classical problems in combinatorial\noptimization: Given a set of items, each specified by its size and profit, the\ngoal is to find a maximum profit packing into a knapsack of bounded capacity.\nIn the online setting, items are revealed one by one and the decision, if the\ncurrent item is packed or discarded forever, must be done immediately and\nirrevocably upon arrival. We study the online variant in the random order model\nwhere the input sequence is a uniform random permutation of the item set.\n We develop a randomized (1/6.65)-competitive algorithm for this problem,\noutperforming the current best algorithm of competitive ratio 1/8.06\n[Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new\ninsights: We introduce a novel algorithmic approach that employs two given\nalgorithms, optimized for restricted item classes, sequentially on the input\nsequence. In addition, we study and exploit the relationship of the knapsack\nproblem to the 2-secretary problem.\n The generalized assignment problem (GAP) includes, besides the knapsack\nproblem, several important problems related to scheduling and matching. We show\nthat in the same online setting, applying the proposed sequential approach\nyields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed\nalgorithm outperforms the current best result of competitive ratio 1/8.06\n[Kesselheim et al. SIAM J. Comp. 47(5)].\n