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:
-
[Motwani-Raghavan]
Problem 5.3 (independent sets)
-
[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)
-
(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.
- 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.
- 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.
-
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.)
- [Mitz-Upfal] Problem 4.4
-
[Mitz-Upfal]
Problem 4.5