Recall the Chernoff bound we proved in class:
the probability that any sum of independent random variables in [0,1]
exceeds its expected value 
by more than a factor of 
is less than 
, where
Let 
so that 
.
Using whatever means you like (a calculator, Mathematica, Maple, or calculus
(e.g. Taylor series)), try to understand and describe the function 
as
best you can. In particular, try to get a reasonable approximation for
(say, within constant factors) in terms of 
and
.
It may help to consider the ranges 
and 
separately.
Proofs of the quality of your approximation would be nice but are not required.
The input is a bipartite graph G=(V,W,E) and a number 
.
The vertices in V are ordered 
,
and each odd vertex forms a couple with the next vertex.
That is, 
and 
form a couple,
and 
form a couple, and so on.
The goal is to choose one vertex from each couple (n vertices in total),
in such a way that no vertex in W has more than of its neighbors
chosen. (This may or may not be possible for any given input.)
No polynomial-time algorithm is known for this problem.
You are to develop and analyze a randomized polynomial-time algorithm for finding an approximate solution.
To start, consider the relaxed problem. The input is the same, but the
goal is to assign non-negative weights to the vertices of V so
that, for each couple, the sum of the weights on the two vertices is 1,
while the total weight on edges incident to any vertex in W
is at most .
- Show how this relaxed version can be formulated as a linear program.
- Suppose that the relaxed problem has a solution p.
Consider the following random experiment. For each couple v,v', choose one of the two vertices at random: choose v with probability p(v) and choose v' with probability p(v') = 1-p(v).
Argue that for any vertex in W, the expected number of chosen neighbors is at most
. - Figure out the smallest
you can so that (using the
Chernoff bound) the probability that any given vertex in W has more
than 
chosen neighbors is less than 1/2|W|. The
value for will depend on . - Argue that the expected number of vertices in W with more than
chosen neighbors is at most 1/2. Why does this mean
that with probability at least 1/2, all vertices in W will have at
most neighbors chosen?
- Combine the above arguments to argue that there is a randomized
algorithm for the original problem that runs in expected polynomial time
and, if a solution exists, finds an approximate solution in that
the number of chosen neighbors of any vertex
is at most 
.
Describe how the quantity
varies as a function of .