The bin packing decision problem

1. The bin packing decision problem is that given an unlimited number of bins, each of capacity 1,
   and n objects with sizes s1, s2, . . . , sn, where 0 < si ≤ 1, do the objects fit in k bins? where k is
   a given integer.
   The bin packing optimization problem is to find the smallest number of bins into which the objects
   can be packed.
   Show that if the decision problem can be solved in polynomial time, then the optimization problem
   can also be solved in polynomial time.
2. Show that if the hamiltonian cycle decision problem can be solved, then the problem of listing the
   vertices of a hamiltonian cycle in order is also solvable.
3. Suppose that we had a polynomial-time subprogram TSP to solve the traveling saleperson decision
   problem (i.e., given a complete weighted graph and an integer k, it determines whether there is a
   tour of total weight at most k.)
   (a) Show how to use the TSP subprogram to determine the weight of an optimal tour in polynomial
   time.
   (b) Show how to use the TSP subprogram to find an optimal tour in polynomial time.

Sample Solution