Homework 9 (Last One!)

CS 482 - Summer 2007

Due: Wednesday, Aug 15

  1. [Approximate Graph Coloring; 5 points] Problem 1 in Chapter 13 of the text.
     
  2. [Protocol for Conflict Resolution; 5 points] Problem 3 in Chapter 13 of the text.
     
  3. [Approximate Max-SAT; 5 points] Problem 7 in Chapter 13 of the text.
     
  4. [Updating the Bid; 5 points] Problem 10 in Chapter 13 of the text.