Lower bounds on the performance of online algorithms for relaxed packing problems
János Balogh et al.
What the paper says
We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: Online Removable Multiple Knapsack , and a recently introduced Online Minimum Peak Appointment Scheduling problem. The high level obwjective in both problems is to pack arriving items of sizes at most 1 into bins of capacity 1 as efficiently as possible, but the exact formalizations differ. In the Minimum Peak Appointment Scheduling problem, every item has to be assigned to a position, which can be seen as a time interval during a workday of length 1. That is, items are not assigned to bins while they are still arriving, but only once all the items are processed, the optimal number of bins subject to chosen positions is determined, and this is the cost of the online algorithm. Here, we improve the known lower bound on the randomized competitive ratio of this problem. On the other hand, in the Removable Multiple Knapsack Problem there is a fixed number of bins, and the goal of packing items, which consists in choosing a particular bin for every packed item (and nothing else), is to pack as valuable a subset as possible. In this last problem it is possible to reject items, that is, deliberately not pack them, as well as to remove previously packed items at any later point in time, for added flexibility. Improved lower bounds on the competitive ratio are given for several variants of the Removable Knapsack Problem, including variants in one dimension and variants of Vector Knapsack in multiple dimensions.
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.