\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{19 November 2014}{20}

\begin{center}
\Large{\bf Problem Set 6 (due Wednesday, December 3)}
\end{center}

{\bf 1. (4 $\times$ 5 = 20 points) NP-completeness}

Problem 34-2 of text.

{\bf 2. (5 $\times$ 3 = 15 points) Maximum-weight spanning tree}

Problem 35-6 of text.

{\bf 3. (5 $\times$ 3 = 15 points) NP-completeness and approximation algorithms}

Let $G$ be an directed graph with $k$ start nodes $s_1$ through $s_k$
and $k$ end nodes $t_1$ through $t_k$.
\begin{itemize}
\item[{\bf (a)}] Give a reduction from 3-SAT to show that it is
  NP-hard to determine whether there exist $k$ paths, the $i$th path
  from $s_i$ to $t_i$, $1 \le i \le k$, such that no two paths share
  an edge.
\end{itemize}

We next consider an optimization version of the above problem.  Here,
we allow paths to share edges, and define the {\em load}\/ $\ell(e)$
on an edge $e$ to be the number of $s_i$-$t_i$ paths that use $e$.
The optimization problem then is to determine a set of $s_i$-$t_i$
paths that minimizes $\max_e \ell(e)$.

\begin{itemize}
\item[{\bf (b)}] Write an integer linear program for the above
  problem.  ({\em Hint:} You can view each $s_i$-$t_i$ path as a flow
  of unit 1 from $s_i$ to $t_i$.)

\item[{\bf (c)}] Develop a randomized rounding algorithm which
  proceeds as follows: Relax the integrality constraint, and solve the
  LP; Decompose each $s_i$-$t_i$ flow into a set of paths (we have
  seen this in a POW in class); Use randomized rounding to select a
  path.  Fill in the details.
\end{itemize}

The next step is to show that the above rounding algorithm will
achieve a load within an $O(\log n)$-factor of the optimal with high
probability, say at least $1 - 1/n$, where $n$ is the number of nodes
in the graph.

\begin{itemize}
\item[{\bf (d)}] Show that the expected load of an edge $e$ is equal
  to the total flow on the edge $e$ in the LP solution.

\item[{\bf (e)}] Using Chernoff bounds (described below) show that
  with probability at least $1 - 1/n$, the load of the path collection
  is within an $O(\log n)$ factor of the optimal achievable load.

{\bf Chernoff bound:} Let $X_1, X_2, \ldots, X_n$ be $n$ independent
random variables each taking a value of $0$ or $1$.  Let $X$ denote
$\sum_i X_i$.  Then, for any $\delta > 0$, we have the following.
\[
\Pr\left[X > (1 + \delta) E[X]\right] \le \left(\frac{e^\delta}{(1 +
    \delta)^{1+\delta}}\right)^{E[X]}.
\]

({\em Hint:} For each edge, use the Chernoff bound to place a very
small upper bound on the probability that the load of the edge exceeds
$O(\log n)$ times the expectation.  Then use a union bound to argue
that with high probability, the load on every edge is within an
$O(\log n)$ factor of the optimal.)
 
\end{itemize}
\end{document}