Due: Wednesday, March 27 at the beginning of class.
From the book: 35.1-1 [page 1111]. You only need to give one graph and a sequence of choices of vertices that APPROX-VERTEX-COVER might make that leads to a choice of vertex cover that is not the smallest possible.
From the book: 35.1-3 [page 1111]. You only need to find one graph and a sequence of choices of vertices that this algorithm might make that leads to a vertex cover whose size is more than twice the optimal size.
From the book: 35.2-3 [page 1117]. Closest point heuristic.
From the book: 35-1(b-d) [page 1134].
From the book: 32.1-2 [page 989].