% \def\solutionMode{TRUE}
\documentclass[11pt]{article}
\usepackage{573}
%
% ======================================================================
\begin{document}
%\thispagestyle{empty}
%\headers{\Course{}}{Homework 0 (due 8/30/07)}{\Semester{}}
\begin{center}
{\LARGE\bf \Course{}: \CourseName{}, \Semester{}}
\\[1ex]
{\Large\bf Homework 3, due Monday, October 28, 23:59:59, \Year}
\\[0.25in]
{\Large\bf Version 1.0}
\end{center}
% ----------------------------------------------------------------------
\medskip
\noindent
Neatly print your name(s), NetID(s) on each submitted question.
Remember that you have to submit each question on a separate
page. each student should submit his own homework. If you are on
campus, submit the homework by submitting it in the homework boxes in
the basement of SC.
% ----------------------------------------------------------------------
\bigskip
%\newpage
%\thispagestyle{empty}
\noindent\fbox{\begin{minipage}{0.99\linewidth} \footnotesize At other
times you seemed to me either pitiable or contemptible,
eunuchs, artificially confined to an eternal childhood,
childlike and childish in your cool, tightly fenced, neatly
tidied playground and kindergarten, where every nose is
carefully wiped and every troublesome emotion is soothed, every
dangerous thought repressed, where everyone plays nice, safe,
bloodless games for a lifetime and every jagged stirring of
life, every strong feeling, every genuine passion, every
rapture is promptly checked, deflected and neutralized
by meditation therapy.\\
$~$~~~~~~~~ -- The Glass Bead Game, Hermann Hesse
\end{minipage}}
\section*{Required Problems}
\newcommand{\GreedyIndep}{\Algorithm{Greedy{}I{n}d{e}p}}
% ======================================================================
\begin{compactenum}[\color{red} \huge \bf 1.]%
%----------------------------------------------------------------------
\item \HWProblem{25}{Prove infeasibility.}{
You are trying to solve a circulation problem, but it is not
feasible. The problem has demands, but no capacity limits on
the edges. More formally, there is a graph $G = (V, E)$, and
demands $d_v$ for each node $v$ (satisfying $\sum_{v \in V} d_v
= 0$), and the problem is to decide if there is a flow $f$ such
that $f(e) \ge 0$ and $f^{in}(v) - f^{out}(v) = d_v$ for all
nodes $v \in V$. Note that this problem can be solved via the
circulation algorithm from Section 7.7 by setting $c_e = +
\infty$ for all edges $e \in E$. (Alternately, it is enough to
set $c_e$ to be an extremely large number for each edge -- say,
larger than the total of all positive demands $d_v$ in the
graph.)
You want to fix up the graph to make the problem feasible, so
it would be very useful to know why the problem is not feasible
as it stands now. On a closer look, you see that there is a
subset $U$ of nodes such that there is no edge into $U$, and
yet $\sum_{v \in U} d_v > 0$. You quickly realize that the
existence of such a set immediately implies that the flow
cannot exist: The set $U$ has a positive total demand, and so
needs incoming flow, and yet $U$ has no edges into it. In
trying to evaluate how far the problem is from being solvable,
you wonder how big the demand of a set with no incoming edges
can be.
Give a polynomial-time algorithm to find a subset $S \subset V$
of nodes such that there is no edge into $S$ and for which
$\sum_{v \in S} d_v$ is as large as possible subject to this
condition. }{}
\item \HWProblem{50}{Flow in vain.}{
\begin{compactenum}[(A)]
\item \points{25} In a standard $s-t$ Maximum-Flow Problem,
we assume edges have capacities, and there is no limit on
how much flow is allowed to pass through a node. In this
problem, we consider the variant of the Maximum-Flow and
Minimum-Cut problems with node capacities.
Let $G = (V,E)$ be a directed graph, with source $s \in V$,
sink $t \in V$, and nonnegative node capacities $\{ c_v \ge
0 \}$ for each $v \in V$. Given a flow $f$ in this graph,
the flow through a node $v$ is defined as $f^{in}(v)$. We
say that a flow is feasible if it satisfies the usual
flow-conservation constraints and the node-capacity
constraints: $f^{in}(v) \le c_v$ for all nodes.
Give a polynomial-time algorithm to find an $s$-$t$ maximum
flow in such a node-capacitated network. Define an $s$-$t$
cut for node-capacitated networks, and show that the
analogue of the Max-Flow Min-Cut Theorem holds true.
\item \points{13} Show that a maximum flow in a network
$G=(V,E)$ can always be found by a sequence of at most
$|E|$ augmenting paths. [Hint: Determine the paths after
finding the maximum flow.]
\item \points{12} Suppose that a flow network $G=(V,E)$ has
symmetric edges, that is, $(u,v) \in E$ if and only $(v,u)
\in E$. Show that the Edmonds-Karp algorithm terminates
after at most $|V||E|/4$ iterations. [Hint: For any edge
(u,v), consider how both $\delta (s,u)$ and $\delta (v,t)$
change between times at which (u,v) is critical.]
\end{compactenum}
}{} {}{}{}
\item \HWProblem{25}{Maximum Flow By Scaling}{
\newcommand{\mFlowByScale}{\Algorithm{maxFlow-By-Scaling}\xspace}
Let $G=(V,E)$ be a flow network with source $s$, sink $t$, and
an integer capacity $c(u,v)$ on each edge $(u,v) \in E$. Let
$C=max_{(u,v) \in E}c(u,v)$.
\begin{compactenum}[(A)]
\item \points{2} Argue that a minimum cut of $G$ has
capacity at most $C|E|$.
\item \points{6} For a given number $K$, show that an
augmenting path of capacity at least $K$ can be found in
$O(E)$ time, if such a path exists.
The following modification of
\textsc{Ford-Fulkerson-Method} can be used to compute a
maximum flow in $G$.
~
\centerline{ \fbox{
\begin{minipage}{0.7\linewidth}
\mFlowByScale{}$(G,s,t)$\\
% \begin{enumerate}
1 \hspace*{0.2in} $C \leftarrow max_{(u,v) \in E}c(u,v)$\\
2 \hspace*{0.2in} initialize flow $f$ to $0$\\
3 \hspace*{0.2in} $K \leftarrow 2^{\floor{\lg{C}}}$\\
4 \hspace*{0.2in} {\bf while} $K \geq 1$ {\bf do} \{\\
5 \hspace*{0.6in} {\bf while} (there exists an
augmenting path $p$ of\\
\hspace*{1.8in} capacity at least $K$) {\bf do} \{\\
6 \hspace*{1.0in} {\bf } augment flow $f$ along
$p$ \\
\hspace*{0.8in}\} \\
7 \hspace*{0.6in} { $K \leftarrow K/2$}\\
\hspace*{0.40in}\} \\
\\
8 \hspace*{0.2in} {\bf return} $f$
% \end{enumerate}
\end{minipage}
} }
~
\item \points{4} Argue that \mFlowByScale returns a maximum
flow.
\item \points{5} Show that the capacity of a minimum cut of
the residual graph $G_f$ is at most $2K|E|$ each time line
4 is executed.
\item \points{5} Argue that the inner {\bf while} loop of
lines 5-6 is executed $O\pth{ \cardin{E} }$ times for each
value of $K$.
\item \points{3} Conclude that \mFlowByScale can be
implemented so that it runs in $O(E^2 \lg{C})$ time.
\end{compactenum}
}{}{}
\end{compactenum}
\end{document}
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------
% ----------------------------------------------------------------------