CSE 421 Assignment #8
Spring 2016

Due: Friday, June 3, 2016.

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 except that you only only need to solve this problem in the case that all the weights are 1.

  4. Extra credit: Extend the solution to problem 3 above to the case of arbitrary weights.