Design and Analysis of Algorithms Neal Young
Computer Science 45
Due: Monday, May 26, 1997
Problem Set 5
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 .
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 .
Describe how the quantity varies as a function of
.