\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphics,epsfig}

\begin{document}
\begin{center}
\bf
Algorithms, Section 2\\
Spring 2003\\
\rm
Homework 11a\\
Due Thursday, April 17 \\
\end{center}

\emph{Reminder:}  The second exam will be given out on Thursday, April 17, in 
class.
It will be due on Tuesday, April 22 in class.  It will be a closed book and
closed notes takehome exam, but you may prepare an $8 \times 11$ sheet of 
notes (both sides) for use when taking it. You will have an unlimited 
amount of time to work on the exam, even though it is designed to only take
four (or fewer) hours to complete. I have this policy because I want 
you to feel no time pressure whatsoever, and I also want to give you plenty
of time to carefully consider and reflect on your solutions.

\begin{enumerate}

\item \textbf{[30 points] Space Shuttle Profit Optimization!}

        After successful careers at Millisoft, Hurts Car Rental, and
        the brokerage firm of Weil, Proffet, and Howe, you've been
        hired by NASA to help optimize their Space Shuttle program.

        On a given mission, NASA will consider a set of experiments
        that industrial sponsors would like to conduct (for example,
        ``Does gravity affect Spam?'').  Let $E = \{ E_{1}, E_{2},
        \ldots, E_{m} \}$ denote the set of experiments under
        consideration.  Let $p_{j}$ denote the amount of money the
        sponsor will pay to conduct experiment $E_{j}$.
        The experiments use a set $I = \{I_{1}, I_{2}, \ldots, I_{n} \}$
        of instruments to conduct the experiments.
        For each experiment $E_{j}$, let $R_{j}$ be the subset of $I$
        that contains all of the instruments needed to conduct
        experiment $E_{j}$.  Notice that this allows a single
        instrument to be used in multiple experiments.
        The instruments are potentially large
        and heavy and the cost of taking instrument $I_{k}$ is $c_{k}$
        dollars.  Your job is to determine which experiments should
        be performed in order to maximize the net revenue, which is
        the total income from the performed experiments minus the
        total cost of all
        instruments carried.  Amazingly, this problem can be solved
        using {\bf network flow}!

        We'll construct a network flow problem as follows:
        The network contains a source vertex, $s$, vertices
        $I_{1}, I_{2}, \ldots, I_{n}$, vertices $E_{1}, E_{2},
        \ldots, E_{m}$, and a sink vertex $t$.
        For each instrument $I_{k}$ there is a directed edge from
        $s$ to vertex $I_{k}$ with capacity $c_{k}$ (the cost of taking this
        instrument).  For each experiment $E_{j}$ there is an edge
        from vertex $E_{j}$ to $t$ with capacity $p_{j}$ (the payment
        for this experiment).
        Finally, if instrument $I_{k}$ is in set $R_{j}$ (meaning that
        instrument $I_{k}$ is needed for experiment $E_{j}$) then
        there is a directed edge from vertex $I_{k}$ to vertex $E_{j}$
        with {\bf infinite} capacity.

        \begin{enumerate}
        \item First, try this.  Consider a situation in which there
        are three experiments $E_{1}, E_{2}, E_{3}$ which will bring
        in $10$, $6$, and $6$ dollars, respectively.  Also there are
        four instruments $I_{1}$, $I_{2}$, $I_{3}$, and $I_{4}$ which
        cost $3$, $2$, $5$, and $7$ dollars, respectively to take on the
        shuttle.  Experiment $E_{1}$ requires instruments $I_{1}$ and
$I_{2}$,
        experiment $E_{2}$ requires instruments $I_{1}$ and $I_{3}$,
        and experiment $E_{3}$ requires instruments $I_{3}$ and
$I_{4}$.  Using brute-force, enumerate all seven possible combinations
        of experiments that could be taken and determine which
combination is the most profitable.  What is this combination and what
is the net revenue?

        \item For the example problem above, construct the
corresponding network flow problem.  Find the maximum flow in the
network (show your residual graphs at each step) and then find the
corresponding cut whose capacity is equal to this flow.

        \item Let's let $S$ denote the vertices that are on the same
side of the above cut as vertex $s$ and let $T$ denote the vertices
that are on the same side of the cut as $t$.  What do you notice about
the instruments and experiments that are in the set $T$?

        \item Now, let $\tau$ be the sum of the payments that NASA
would receive for taking all of the possible experiments.  In this
case, $\tau = 10 + 6 + 6 = 22$.  From $\tau$, subtract the capacity
of the cut you found above.  Surprise!  What is this number and how
does it appear to relate to this problem?

        \item Finally, we're ready to generalize all of this into
an efficient algorithm for solving the profit maximization problem in
general.  Assume that we've set up a network flow problem
corresponding to a given set of experiments and instruments.
Show that for any cut with finite total capacity, if an experiment
$E_{j}$ is in $T$ (the side of the cut containing vertex $t$), then
all of the instruments used in this experiment must {\bf also} be in
$T$.

        \item Now argue that the maximum net revenue that can be
achieved is simply the total sum $\tau$ of the payments that would
be received for taking all of the experiments minus the capacity
of the minimum cut.

        \item Now just summarize all of this by describing the
algorithm, step-by-step, for finding the maximum net revenue, given
a set of experiments, instruments, and the corresponding payments and
costs.  Give a careful derivation of the worst-case running time of
the algorithm assuming there are $m$ experiments and $n$ instruments.

\end{enumerate}

\end{enumerate}


\end{document}

