Consider a combinatorial auction with m items numbered from 1 to m. Assume that each bidder is single-minded (i.e., is only interested in acquiring a specific bundle of items) and desires an interval of consecutively numbered items. Prove that an efficient allocation (i.e., an allocation that maximizes the social welfare) can be determined in polynomial time. Hint: Use dynamic programming. CLARIFICATION ADDED 4/19/12: You should assume that you are given, for each bidder i, the bundle of items Si that bidder i is interested in, along with the nonnegative value vi that bidder i assigns to Si