CSE 421 Assignment #8
Autumn 2012

Due: Wednesday, December 5, 2012.

Reading Assignment: Kleinberg and Tardos Section 11.3

Problems: For all problems on this homework that involve proving NP-completeness, give a full argument that shows that your reduction is correct and runs efficiently and make sure to prove that your problem is in NP also. If you are giving an algorithm, prove that your algorithm is correct and show that it runs efficiently.

  1. Kleinberg and Tardos, Chapter 8, Problem 14, page 512.

  2. Solve Kleinberg and Tardos, Chapter 8, Problem 13, page 511 except show that the problem is NP-complete even if the input has an extra condition that every bidder's bid is for a set of exactly 3 items. (Call this the Winner Determination for Combinatorial Auctions with Triple Bids problem or WDCATB for short.)

  3. Kleinberg and Tardos, Chapter 11, Problem 4, page 653. UPDATE: You only need to solve this problem if all the weights are 1. Extending this to the case of arbitrary weights will be for extra credit. will be

  4. Extra credit: Kleinberg and Tardos, Chapter 8, Problem 31, page 520.