Online Unbounded Knapsack

• DOI: 10.48550/arxiv.2407.02045
• Publication Date: 2024-07-02
• Authors: Hans-Joachim Böck...; Matthias Gehnen; Juraj Hromkovič; Ralf Klasing; Dennis Komm; Henri Lotze; Daniel Mock; Peter Rossmanith; M. Stocker
• Keywords: Advice complexity; FOS: Computer and information sciences; online algorithm; advice complexity; Online algorithm; Computer Science - Data Structures and Algorithms; Unbounded knapsack; Data Structures and Algorithms (cs.DS); unbounded knapsack; online knapsack; Online knapsack

We analyze the competitive ratio and advice complexity of online unbounded knapsack problem. An instance is given as a sequence n items with size value each, an algorithm has to decide how often pack each item into bounded capacity. The are total packed must not exceed knapsack's capacity, while objective maximize items. While can only be once in classical 0-1 problem, version allows for multiple times. show that simple where equal its value, 2. also randomized algorithms that, contrast one uniformly random bit cannot improve algorithm's performance. More randomness lowers less than 1.736, but it never below 1.693. In setting, we measure many bits information know achieve some desired solution quality. For 3/2. this improved fewer log(n) instances length n, 1+epsilon achieved O(log(n/epsilon)/epsilon) any epsilon>0. further no amount by function f(n) optimal. study general problem does allow deterministic algorithms, well using bits. provide uses