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

\head{CSG399}{Algorithmic Power Tools}{Fall 2007}{2 November 2007}{2}

\begin{center}
\Large{\bf Problem Set 2 (due Tuesday, November 27))}
\end{center}

\noindent {\bf Grading.}  This problem set has a total of 125 points.
We plan to have three problem sets in all, for a total of at least 300
points.  From a grading perspective, the total points allocated for
problem sets is 200 points.  So you should plan on attempting at least
200 points in all, over all problem sets.  Any score you earn beyond
the basis of 200 points will be bonus points for you.

\noindent {\bf Collaboration.} You are welcome to collaborate on
solving these problems.  But you must write the solutions on your own.
Please cite any collaborators and/or references that help you in
arriving at your solutions.

{\bf 1. (25 points) Synchronized duals for set cover}

A primal-dual approach that we have studied is to start with a
feasible dual solution and then raise a certain subset of the dual
variables until some dual constraint became tight, at which point we
set the associated primal variable appropriately.  For the Steiner
Forest problem in particular, we studied a scheme in which we raise a
set of ``active'' dual variables simultaneously at a uniform rate
until some edge became tight.

In this problem, we analyze the same approach for set cover.  Consider
the following algorithm.  Recall that we have a primal variable $x_S$
for each set $S$ in the collection of sets and a dual variable $y_e$
for each element of the universe.
\begin{itemize}
\item
Set all $y_e$ to $0$.  Initialize set cover $F$ to $\emptyset$.
\item
Repeat the following steps until all elements are covered.
\begin{itemize}
\item
Raise the dual variable $y_e$ for each uncovered element uniformly
until some set $S$ becomes ``tight'' (i.e., $\sum_{e \in S} y_e =
c(S)$).
\item
Add $S$ to $F$ and remove any sets all of whose elements have been
covered.  (If multiple sets become tight, let $S$ denote an arbitrary
one tight set.)
\end{itemize}
\item Return $F$.
\end{itemize}

Show that the above algorithm has an approximation ratio of at most
$f$, where $f$ is the {\em maximum frequency}, the maximum number of
sets that contain a given element.  Show that for any value of the
maximum frequency $f$, there exists an instance for which the
algorithm's approximation ratio is at least $f - \eps$, where $\eps >
0$ can be made arbitrarily small.

{\bf 2. (25 points) Including tight edges in primal-dual algorithm for
Steiner Forest}

The Goemans-Williamson primal-dual algorithm we studied in class
includes only one tight edge in any iteration.  We discussed the
primal-dual algorithm in which we include all tight edges in an
iteration, and in the last step consider edges in arbitrary order,
removing any edge that forms a cycle.

Show that if the order of edges in the last step is unspecified, then
the above algorithm is $\Omega(n)$-approximate, where $n$ is the
number of nodes.  

({\em Hint:} Devise an example in which we add light-weight edges
followed by several heavy-weight edges (all in a single iteration),
and then in the edge deletion step, we first remove the light-weight
edges since they are part of some cycle.)

{\bf 3. (25 points) Initial solution for $k$-median local search}

The running time of the local search algorithm for $k$-median is
simply the number of iterations times the time taken for each local
search iteration.  Since the latter is fixed, it makes sense to keep
the number of iterations small.  One way toward this is to start with
a reasonable initial solution.  Assume for simplicity that all points
have unit demand and a facility can be potentially opened at any
point.  Consider the following initial solution.

\begin{itemize}
\item
$S \leftarrow \emptyset$.

\item
For $i$ from $1$ to $k$:
\begin{itemize}
\item 
Let $u$ be a point whose distance to the current set is largest; that
is, $d(u, S) \ge d(v, S)$ for all $v$, where $d(v,S)$ is defined as
$\min_{w \in S} d(v,w)$.

\item Add $u$ to $S$.
\end{itemize}
\end{itemize}

\begin{itemize}
\item[{\bf (a)}] Let $S$ be the set of points returned by the above
algorithm and let $T$ be an arbitrary set of $k$ points.  Prove that
for 
\[
\max_{v} d(v, S) \le 2\cdot \max_v d(v, T).
\]

({\em Hint:} One approach is to use induction on $k$, the number of
points in $S$ and $T$.  The base case is easy.  For the induction
step, consider two cases.  One case is when there exists a point $t$
in $T$ for which there are at least two points in $S$, whose closest
point in $T$ is $t$.  The other case is when for every point $t$ in
$T$, there is exactly one point in $S$ whose closest point in $T$ is
$t$.)

\item[{\bf (b)}] Using part (a), prove that the above algorithm yields
a $k$-median solution that is $O(n)$-approximate.

{\bf Remark:} While this is not a good approximation ratio, the fact
that it is independent of the value of the distances in the metric
makes it useful to show that the running time of local search, used
with this procedure, is strongly polynomial time.)
\end{itemize}

{\bf 4. (25 points) LPs for multicommodity flow.}

Consider the demands version of the multicommodity flow problem.   We
are given a graph $G = (V, E)$ with capacity on edges given by $c_e, e
\in E$, a set of $k$ source-sink pairs $(s_i, t_i)$, $1 \le i \le
k$ with demands given by $d_i$, $1 \le i \le k$.  The goal is to
determine the largest $f$ such that $f \cdot d_i$ flow of the $i$th
commodity can be sent from source $s_i$ to sink $t_i$, for $1 \le i
\le t$, subject to the flow conservation and capacity constraints.

In our class (when we covered the Leighton-Rao result), we wrote the
following dual LP for the path-flow-based LP.

\begin{eqnarray}
\min & \sum_{e \in E} c_e d_e & \nonumber\\
\sum_{e \in p^j_i} d_e & \ge & l_i \, \mbox{    } \forall \mbox{ $s_i-t_i$ path } p^j_i \label{eqn:lp1}\\
\sum_{1 \le i \le k} l_i & \ge & 1 \nonumber
\end{eqnarray}

\begin{itemize}
\item[{\bf (a)}] Write down an alternative linear program for the
demands multicommodity flow problem based on edge flows.  In
particular, have a variable $x^i_{(u,v)}$ for each edge $(u,v)$ and
commodity $i$ that represents the flow of commodity $i$ from $u$ to
$v$.  Complete the LP by capturing the objective function, the flow
conservation constraints, and capacity constraints in terms of these
``edge flow'' variables.

\item[{\bf (b)}] Write a dual for the linear program from part (a).
Compare this dual with the LP given by Equation~\ref{eqn:lp1}.

\item[{\bf (c)}]
Using part (b) or otherwise (e.g., using the separation oracle
method), show that LP~\ref{eqn:lp1} can be solved in polynomial time.
\end{itemize}

\junk{
{\bf 5. (20 points) Duality for multicommodity flow.}

For the single-commodity case, the duality concept yields the max-flow
min-cut theorem.  In the multi-commodity case, however, we saw that
one natural generalization of this theorem (max-demands flow =
sparsest cut) is not true.  But surely the duality principle applied
to the multicommodity flow LPs should yield some max-flow-min-cut-like
theorem?  In this exercise, we explore one such relationship.

Consider the primal and dual LPs for the demands multicommodity flow
problem we studied in class.  For simplicity, assume that the demand
for every commodity is uniform.  Let $d$ denote a dual solution: $d_e$
is the distance label on edge $e$ in the dual solution.  The edges
with distance labels $0$ define a set of equivalence classes among the
nodes: two nodes $u$ and $v$ are in the same equivalence class if they
are at distance zero from each other.  Let $S_i$, $1 \le i \le k$
denote the equivalence classes thus obtained.

\begin{itemize}
\item[{\bf (a)}]
Show that for any two edges $e$ and $e'$ connecting $S_i$ to $S_j$, $i
\neq k$, $d^*_{e} = d^*_{e'}$.

\item[{\bf (b)}] Based on (a), now define $d^*_{ij}$ to be the
distance label of any edge connecting $S_i$ to $S_j$.  Show that the
primal and dual optimum values equal 
\[
\sum_{1 \le i < j \le k} d^*_{ij} C_{ij},
\]
where $C_{ij}$ is the total capacity of all the edges between $S_i$
and $S_j$.

\item[{\bf (c)}] Show that 

\[
\min_{w} \frac{\sum_{1 \le i < j \le k} w_{ij} C_{ij}}{\sum_{1 \le i < j \le k} w_{ij} D_{ij}},
\]
where $w$ satisfies symmetry and triangle inequality. $C_{ij}$ is the
total capacity of all the edges between $S_i$ and $S_j$, and $D_{ij}$
is the sum of demands for commodities with source in $S_i$ and sink in
$S_j$ or vice versa.
\end{itemize}
}

{\bf 5. (25 points) Unsplittable multicommodity flow}

In the multicommodity flow problem we defined in class, we assumed
that a flow from a source to a sink can be split among multiple
paths.  In some applications, especially in the networking domain, one
may demand flow of a single commodity to be sent along a single path.
We call this the unsplittable multicommodity flow problem.

\begin{itemize}
\item[{\bf (a)}] Show that the unsplittable multicommodity flow
problem is NP-hard, even with two commodities. 

({\em Hint:} Reduce from the partition problem.)
\end{itemize}

Consider the special case of the demands version of the unsplittable
multicommodity flow problem in which the demand of each commodity as
well as the capacity of each edge is $1$.  We study the following
randomized rounding algorithm for unsplittable multicommodity flow in
this case.

\begin{enumerate}
\item
Solve the LP relaxation of the problem (which removes the
unsplittability constraint).

\item
Decompose the flow of each commodity $i$ into a set $P_i$ of at most
$m$ flow paths, where $m$ is the number of edges.  For each commodity
$i$, select a path at random from $P_i$ with probability equal to the
flow of $i$ along the path.  Send all the flow for commodity $i$ (as
determined by the LP) along this path.  Call the resulting flow $f$.

\item
Return the flow obtained by scaling $f$ down by the largest amount of
flow going across any edge.
\end{enumerate}

\begin{itemize}
\item[{\bf (b)}] Prove that after step 2 of the above algorithm, the
expected flow along any edge is at most 1.

\item[{\bf (c)}] Prove that after step 2, the flow along any edge is
at most $O(\log n)$ with probability at least $1 - 1/n^3$.

{\em Hint:} Use Chernoff bounds.  See the theorem on relative error
in the following wikipedia entry.

http://en.wikipedia.org/wiki/Chernoff\_bounds

\item[{\bf (d)}] Conclude that the above algorithm yields an
unsplittable multicommodity flow whose value is at most an $O(\log n)$
factor less than that of an optimal unsplittable multicommodity flow,
with probability at least $1 - 1/n$.
\end{itemize}
\end{document}

