8 - Knapsack

Summary

Introduction

In this chapter, we discuss the online version of one of the most versatile combinatorial problems, called the knapsack. In the classical offline version of the knapsack problem, we are provided with a set of items I and a knapsack of size or capacity C. Each item i * I has value v(i) and size w(i), and the problem is to select a subset of I that maximizes the sum of the value of the selected items, subject to the sum of the sizes of the selected items being less than the capacity C of the knapsack.

Because of the two unrelated attributes for each item, value and size, the knapsack problem is sufficient to model various real-world problems where the objective is to maximize a utility function subject to an independent capacity constraint. Important examples of the knapsack problem are scheduling with resource capacity constraints, budgeted auctions, combinatorial resource allocation, etc.

In the online version, the knapsack capacity constraint is available ahead of time, but each item is presented sequentially when its value and size are revealed. An item on its arrival has to be permanently accepted or rejected, irrevocably. It is worth mentioning that the secretary problem considered in Chapter 7 is a special case of the online knapsack problem, where the size of each item is 1 and the knapsack capacity is also 1. Thus, unfortunately, the result that no algorithm is competitive for the secretary problem under the adversarial input carries over for the knapsack problem. Therefore, in this chapter, we primarily consider the secretarial input and present an online algorithm whose competitive ratio is a constant.

We show that a randomized algorithm based on the sample and price philosophy is 1/10ecompetitive in expectation for the knapsack problem with the secretarial input model. We also consider the worst-case input, though with resource augmentation, where an online algorithm is allowed more capacity than the optimal offline algorithm, and an online algorithm is also allowed to reject previously accepted items.