\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 2010}{29 October 2010}{11}

\begin{center}
\Large{\bf Problem Set 4 (due Monday, November 8)}
\end{center}

{\bf 1. (5 + 2 + 3 = 10 points)} {\bf Pathalogical example for the
  basic augmenting path algorithm}

In the residual network $G_f$ corresponding to a flow $f$, define an
{\em augmenting walk}\/ as a directed walk from source $s$ to sink $t$
that visits any arc at most once (it might visit nodes multiple
times-- in particular, an augmenting walk might visit nodes $s$ and
$t$ multiple times).  Define the {\em residual capacity}\/ of an
augmenting walk to be the residual capacity (i.e., capacity in $G_f$)
of the minimum-capacity edge in the walk.

\begin{itemize}
\item[{\bf (a)}] 
Consider the network shown in Figure~\ref{fig:pow13}(a) with the edges
labeled $a$, $b$, $c$, and $d$; note that one arc capacity is
irrational.  Show that this network contains an infinite sequence of
augmenting walks whose residual capacities sum to the maximum flow
value.  ({\em Hint} : Each augmenting walk of the sequence contains
exactly two arcs from node $s$ to node $t$ with finite residual
capacities.)

\begin{figure}[htb]
\input{Figures/network.tex}
\caption{\small A pathological example for the basic augmenting path algorithm.}
\label{fig:pow13}
\end{figure}

\item[{\bf (b)}] 
Now consider the network shown in Figure~\ref{fig:pow13}(b).  Show
that this network contains an infinite sequence of augmenting walks
whose residual capacities sum to a value different than the maximum
flow value.

\item[{\bf (c)}] 
Next consider the network shown in Figure~\ref{fig:pow13}(c); in
addition to the edges shown, the network contains an infinite capacity
edge connecting each node pair in the set $\{1, 2, 3, 4\}$ as well as
each node pair in the set $\{1', 2', 3', 4'\}$.  Show that each
augmenting walk in the solution of part (b) corresponds to an
augmenting path in Figure~\ref{fig:pow13}(c).  Conclude the basic
augmenting path algorithm, when applied to a maximum flow problem with
irrational capacities, might perform an infinite sequence of
augmentations and the terminal flow value might be different than the
maximum flow value.
\end{itemize}

{\bf 2. (10 points) Covering the 2012 London Summer Olympics}

A major sports broadcaster wants to send a group of reporters to cover
a set of sporting events in the London Summer Olympics.  The sports
events will be held in several stadiums and venues in and around the
London area.  We know the starting time and ending time of each event,
and the location where it is held.  We are also given the travel time
between different locations.  Design a polynomial-time algorithm to
determine the least number of reporters needed to cover these events.
Justify its correctness and analyze its running time.

({\em Hint:} Given a positive integer $k$, determine whether $k$
reporters suffice by solving an appropriate network flow problem.)

{\bf 3. (10 points) Tight-knit communities in social networks}

Social networks are all the craze these days.  Assuming that
friendship links are symmetric, one can represent a social network
such as Facebook as an undirected unweighted graph $G$.  Identifying
clusters, communities, and other connectivity properties is a hot
topic of research.

Suppose you want to identify a tight-knit community in a social
network $G$.  For a given set $S$ of nodes in $G$, let $n(S)$ denote
the number of edges with both endpoints in $S$.  Define the {\em
  bonding}\/ of any set $S$ of nodes in $G$ to be $n(S)/|S|$.  Larger
the $n(S)$, the more tight-knit $n(S)$ is; dividing by $|S|$
normalizes across sets of different sizes.

\begin{itemize}
\item[{\bf (a)}] Give a polynomial time algorithm that takes a
  rational number $\alpha$ and determines whether there exists a set
  $S$ with bonding at least $\alpha$.

\item[{\bf (b)}] Use the above algorithm to find a set $S$ of nodes
  with maximum bonding.
\end{itemize}

{\bf 4. (10 points) Single-variable Linear Program}

Exercise 29.5-9 of text.

{\bf 5. (3 + 7 = 10 points) Markov chains and LP duality}

A Markov chain is a set of states (of a system) and the probability,
for each pair of states, of transitioning from one state to the other.
Markov chains have a wide range of applications including as models
for several physical or biological processes, in economics and the
social sciences, web search, and statistics.

Formally, a Markov chain is an $n \times n$ matrix $P$ where $p_{ij}$
denotes the probability of transitioning from state $i$ to state $j$;
if the system is in state $i$ at time $t$, then the probability that
it is in state $j$ at time $t+1$ is $p_{ij}$.  Clearly, $P$ satisfies
the property that the sum of the entries along any row is $1$.  

One nice, and very useful, property of Markov chains is the existence
of a stationary distribution $\pi$ over the state space, where $\pi$
is an $n \times 1$ vector with $\pi_i$ being the probability of the
system being in state $i$.  We say that $\pi$ is stationary if the
following holds: if at any time $t$, $\pi$ gives the probability
distribution for the state of the given system, then $\pi$ is also the
probability distribution for the state in time $t+1$.

For any Markov chain matrix, the existence of a stationary
distribution $\pi$ can be shown easily using LP duality, as we
establish in this exercise.
\begin{itemize}
\item[{\bf (a)}]
Write an LP (over variables $\pi_i$) whose constraints define the
stationary distribution.  Set $\sum_i \pi_i$ as the objective function.

\item[{\bf (b)}]
Derive the dual for the above LP.  Analyze the dual and argue that the
primal is always feasible.
\end{itemize}
\end{document}
