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.