Lower bounds on the performance of online algorithms for relaxed packing problems

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.