CS 466/666

Monday November 12

To sign up for a problem, send email to alubiw "at" uwaterloo.ca. I will update this list to indicate the first person who signs up.
  1. [Nick Wray] Prove that if there is a polynomial time approximation algorithm Vertex Cover that guarantees an solution within an additive constant of the optimum, then P = NP.

  2. [Mike Sage] Prove that the greedy Vertex Cover algorithm can produce a cover C with |C| / OPT in Omega(log n).

  3. [Samantha Breslin] Prove that the decision version of MAX CUT is NP-complete.

  4. [Sean Cumming] For Max 2-SAT prove that the expected number of clauses satisfied by a random truth value assignment is at least m/2, hence at least OPT/2. Here m is the number of clauses. Show that the approximation factor is better if clauses are bigger.

  5. [Jenny Wang] Formulate the general set packing problem and show that any set packing problem can be transformed in polynomial time to the graph independent set problem. If possible, say something about the difference between this situation and the situation with set covering and the graph version (vertex cover).