Homework 2

Linji will hold office hours on Monday March 1 from 3-5pm in Klaus 2210.

The homework is due at class on Tuesday, March 2.
It's best if you can type your solutions using Latex or some other editor such as LyX.
If you hand-write your solutions, make sure they are nicely written so it's easy to read.

Late homeworks: Homeworks can be emailed by the start of class on Thursday, March 4, but 20% will be deducted.
    Homework problems:
  1. [Motwani-Raghavan] Problem 5.3 (independent sets)
  2. [Motwani-Raghavan] Problem 11.2 (#DNF)
    In the language I presented in class, we are generating a random star, and
    then we let Xt = 1/(#stars in the row for assignment a)
    Note, η = |U'| = (total # of stars)
  3. (This problem is from [Kleinberg-Tardos].)
    In class we saw a 3/4-approximation algorithm for the MAX-SAT problem.
    Here we will see a simpler .6-approximation algorithm for the MAX-SAT problem.
    The input is a boolean formula in CNF on n variables and m clauses.
    Assume each clause has at least one term in it, and all the variables
    in a single clause are distinct. But we do not make any other assumptions
    on the length of the clauses.
    1. Recall the simple randomized algorithm we saw in class which yielded a 1/2-approximation algorithm
      for the MAX-SAT problem. Show that there are instances for which no assignment satisfies more than half the clauses.
    2. If we have a clause that consists of only a single term (e.g., (x1)) then there
      is a single way to satisfy it. If we have two clauses such that one consists of just the term xi
      and the other consists of just the negated term xi , then this is a pretty direct contradiction,
      so we will refer to that as a pair of conflicting clauses.
            Assume that our input instance has no pair of conflicting clauses.
      Modify the randomized procedure used in part (a) to improve
      the expected approximation factor from 1/2 to at least .6.
      You need to modify the algorithm from (a) so that the expected number of clauses
      satisfied is at least .6 when there are no conflicting clauses.
    3. Using the procedure from part (b), show how to get a randomized algorithm that
      in expectation achieves a .6-approximation factor for any instance.
      (Note, we are aiming to satisfy at least a .6 fraction of the maximum that can be
      satisfied by an optimal assignment.)
  4. [Mitz-Upfal] Problem 4.4
  5. [Mitz-Upfal] Problem 4.5