\documentstyle{article}

\newcommand{\R}{{\sf R\hspace*{-0.9ex}\rule{0.15ex}{1.5ex}\hspace*{0.9ex}}}
\newcommand{\N}{{\sf N\hspace*{-1.0ex}\rule{0.15ex}{1.3ex}\hspace*{1.0ex}}}
\newcommand{\Q}{{\sf Q\hspace*{-1.1ex}\rule{0.15ex}{1.5ex}\hspace*{1.1ex}}}
\newcommand{\C}{{\sf C\hspace*{-0.9ex}\rule{0.15ex}{1.3ex}\hspace*{0.9ex}}}
       
\setlength{\topmargin}{-0.8in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.25in}
\pagestyle{empty}

\begin{document}

\noindent
{\large Design and Analysis of Algorithms \hfill Neal Young}

\noindent
{\large Computer Science 45 \hfill}

\noindent
{\large Due: Monday, May 26, 1997 \hfill}

\vspace{.3in}

{\LARGE 
\begin{center}
Problem Set 5
\end{center}}
\vspace{.2in}

\begin{enumerate}

\item

  Recall the Chernoff bound we proved in class:
  the probability that any sum of independent random variables in $[0,1]$
  exceeds its expected value $\mu$ by more than a factor of $1+\epsilon$
  is less than $\alpha(\epsilon)^\mu$, where
  $$\alpha(\epsilon) = \frac{e^\epsilon}{(1+\epsilon)^{1+\epsilon}} < 1.$$

  Let $\beta(\epsilon) = \ln 1/\alpha(\epsilon)$
  so that $\alpha(\epsilon) = e^{-\beta(\epsilon)}$.

  Using whatever means you like (a calculator, Mathematica, Maple, or calculus
  (e.g. Taylor series)), try to understand and describe the function $\beta$ as
  best you can.  In particular, try to get a reasonable approximation for
  $\beta$ (say, within constant factors) in terms of $\epsilon$ and
  $\epsilon^2$.

  It may help to consider the ranges $\epsilon \le 1$ and $\epsilon \ge 1$
  separately.

  Proofs of the quality of your approximation would be nice but are not
  required.

\item  Consider the following problem:

  The input is a bipartite graph $G=(V,W,E)$ and a number $\ell$.
  The vertices in $V$ are ordered $v_1,v_2,\ldots,v_{2n}$,
  and each odd vertex forms a {\em couple} with the next vertex.
  That is, $v_1$ and $v_2$ form a couple,
  $v_3$ and $v_4$ 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 $\ell$ 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 {\em approximate} solution.

  To start, consider the {\em 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 $\ell$.

  \begin{enumerate}

    \item Show how this relaxed version can be formulated as a linear program.

    \item Suppose that the relaxed problem has a solution $p$.

      Consider the following random experiment.  For each couple $v,v'$, choose
      {\em 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 {\em expected} number of chosen
      neighbors is at most $\ell$.

    \item Figure out the smallest $\epsilon>0$ you can so that (using the
      Chernoff bound) the probability that any given vertex in $W$ has more
      than $(1+\epsilon)\ell$ chosen neighbors is less than $1/2|W|$.  The
      value for $\epsilon$ will depend on $\ell$.

    \item Argue that the expected number of vertices in $W$ with more than
      $(1+\epsilon)\ell$ 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 $(1+\epsilon)\ell$ neighbors chosen?

    \item 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 {\em approximate} solution in that
      the number of chosen neighbors of any vertex $w\in W$ is at most $\ell +
      \epsilon \ell$.

      Describe how the quantity $\epsilon \ell$ varies as a function of $\ell$.

    \end{enumerate}
  \end{enumerate}
\end{document}
