(Duality Gap of the Knapsack Problem) Given objects i = 1,...,n with positive weights wi and values vi, we want to assemble a subset of the objects so that the sum of the weights of the subset does not exceed a given T > 0, and the sum of the values of the subset is maximized. This is the knapsack problem, which is a special case of a generalized assignment problem
so that the relative value of the duality gap tends to 0 as k → ∞. Note: This exercise illustrates a generic property of many separable problems with integer constraints: as the number of variables increases, the duality gap decreases in relative terms (see Bertsekas [1982], Section 5.5, or Bertsekas [1995b], Section 5.1, for an analysis and a geometrical interpretation of this phenomenon).