% -*- 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}
