ABSTRACT
Chapter 2 considered the problem of allocating multiple items to a single resource, i.e., the knapsack. In the knapsack problem, we have a set of items, from which we need to select a single subset of these items to allocate to the knapsack, with a goal of maximizing the value of the subset of items in the knapsack. We can thus view the knapsack problem as one of packing the knapsack with a subset of items that provides the highest value. A more general version of a so-called packing problem would permit selecting multiple subsets of items such that the subsets are disjoint (i.e., no single item is contained in multiple selected subsets) and each selected subset is allocated to a dierent resource. A distinguishing feature of these packing problems lies in the fact that the union of the subsets selected is not required to contain every item in the original set. In contrast, if we retain the requirement that the selected subsets must be disjoint, but require in addition that each item in the original set must be contained in some selected subset, then instead of a packing problem, we have a partitioning problem. For partitioning problems, our goal may again be to maximize the total value of all selected subsets, or we may cast the problem in terms of the cost associated with allocating a subset to a resource, in which case the objective is to minimize the total cost associated with the chosen subsets. Taking this a step further, if we remove the requirement that the selected subsets must be disjoint (but retain the requirement that each of the original items must be included in at least one selected subset), then we have a so-called covering problem. In this version of the problem, the solution must be such that each item is allocated to (or covered by) at least one resource.
