% -*- compile-command: "rubber -d --unsafe hw-09-flow.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=9,date=November\ 8,topic=Flow\ networks]{algorithms-hw}
\begin{document}
\coversheet
\begin{question} \label{q:FFtime}
\marginnote[0.2in]{\emph{\ref{q:FFtime}}\quad\qrcode{How\ many\
times\ could\ the\ loop\ possibly\ execute\ in\ the\ worst\
case?\ \ How\ long\ does\ it\ take\ to\ find\ an\ augmenting\
path,\ augment\ the\ flow,\ and\ compute\ a\ new\ residual\
network?}} Explain how the Ford-Fulkerson algorithm can be
implemented to run in $O(m \cdot \min(C_s, C_t))$ time (assuming that the edge
capacities are all nonnegative integers), where $m$ is the number of
edges in the network, $C_s$ is the total capacity of all edges
leaving the source node $s$, and $C_t$ is the total capacity of all
edges entering the sink node $t$.
\end{question}
\begin{question} \label{q:matching}
Let $G = (V,E)$ be a bipartite graph with $V = L \cup R$ (that is,
every edge in $G$ has one endpoint in $L$ and one in $R$). A
\emph{matching} in $G$ is a set of edges $M \subseteq E$ such that
no two edges in $M$ share an endpoint. A \emph{maximum matching} is
a matching with the greatest possible number of edges.
\marginnote{\emph{\ref{q:matching}}\quad\qrcode{Create\ a\ network\
G'\ such\ that\ a\ maximum\ flow\ in\ G'\ corresponds\ to\ a\
maximum\ matching\ in\ G.}} Design an algorithm to find a
maximum matching in a given bipartite graph. Describe your
algorithm, prove its correctness, and analyze its running time.
\end{question}
\begin{question}[K\&T 7.6] \label{q:clients}
Consider a set of mobile computing clients in a certain town who
each need to be connected to one of several possible \emph{base
stations}. We'll suppose there are $n$ clients, with the position
of each client specified by its $(x,y)$ coordinates in the plane.
There are also $k$ base stations; the position of each of these is
specified by $(x,y)$ coordinates as well.
We wish to connect each client to exactly one of the base stations,
but our choice of connections is constrained in the following ways.
First, there is a \emph{range parameter}, denoted by $r$: a client
can only be connected to a base station that is within distance $r$.
There is also a \emph{load parameter} $L$: no more than $L$ clients
can be connected to any single base station.
\marginnote{\emph{\ref{q:clients}}\quad\qrcode{Again,\ create\ an\
appropriate\ flow\ network.}} Your goal is to design a
polynomial-time algorithm for the following problem. Given the
positions of a set of clients and a set of base stations, as well as
the range and load parameters $r$ and $L$, decide whether every
client can be connected simultaneously to a base station, subject to
the constraints $r$ and $L$.
\end{question}
\end{document}