\ifx\bookMode\undefined%
\documentclass[11pt]{article}%
\usepackage{caption}%
\usepackage{473} %
\usepackage{473extra} %
\begin{document}
\newcommand{\StandAloneMode}[1]{#1}%
\newcommand{\BookMode}[1]{}%
\fi

\newcommand{\distGY}[2]{d\pth{#1, #2}}%

\newcommand{\costX}[1]{\mathrm{cost}\pth{#1}}%

\noindent\textbf{\LARGE H{}W 10 (due Wednesday, at noon, November 28, \Year)}\\
\noindent{\textbf{\Course: \CourseName, \Semester}}
\hfill\Version{1.22}%
\\[-0.12cm]
\Hr

\noindent%

Submission guidelines and policies as in homework 1.

\Hr

\SaveIndent%
\begin{questions}
    
    \item \HWProblem{100}{Diminishing returns.}%
    {%
       You are running a company with $n$ workers -- let $W$ be this
       set of worker. You have to do a new project, and you would like
       to assign as few people to do the project as possible.  The
       project has $\tau \leq n$ tasks that needs to be completed
       ($\tau$ is a positive integer).  Given a subset
       $S \subseteq W$, you have a function $f(S)$ that tells you the
       number of tasks in the project this group of people can
       complete on their own (i.e., $f(S)$ is an integer
       number). Note, that $f(W) = \tau$ (i.e., if you assign
       everybody to the project, then it can be done in full).
       
       We are going to assume (maybe unrealistically) that the
       function is monotone, that is
       \begin{equation*}
           \forall X \subseteq Y \subseteq W \qquad f(X) \leq f(Y).
       \end{equation*}
       
       Another assumption, known is economics as \emphi{diminishing
          returns}, is that the ``value'' of a single worker decreases
       as we consider bigger sets. Formally, for any $w \in W$, we
       have
       \begin{equation*}
           \forall X \subseteq Y \subseteq W \qquad f(X + w) - f(X)
           \geq f(Y+w) - f(Y),
       \end{equation*}
       where $X + w = X \cup \brc{w}$.
       
       Provide a $O( \log n)$ approximation algorithm to the smallest
       set $Z \subseteq W$, such that $f(Z) = \tau$. Prove the quality
       of approximation of your algorithm. You can assume that
       computing $f$ on a single set, takes $O(n)$ Time. What is the
       running time of your algorithm?
       
    }{}{}{}
    
    \item \HWProblem{100}%
    {Linear programming}%
    {%
       \begin{questions}
           \item \points{10} Show the following problem in \NPHard.
           \NPProblem{Integer Linear Programming} {A linear program in
              standard form, in which $A$ and $B$ contain only
              integers.}  {Is there a solution for the linear program,
              in which the $x$ must take integer values?}
           
           \item \points{50} A steel company must decide how to
           allocate next week's time on a rolling mill, which is a
           machine that takes unfinished slabs of steel as input and
           produce either of two semi-finished products: bands and
           coils. The mill's two products come off the rolling line at
           different rates:
           \begin{center}
               Bands 200 tons/hr\\
               Coils 140 tons/hr.
           \end{center}
           They also produce different profits:
           \begin{center}
               Bands \$ 25/ton\\
               Coils \$ 30/ton.
           \end{center}
           Based on current booked orders, the following upper bounds
           are placed on the amount of each product to produce:
           \begin{center}
               Bands 6000 tons\\
               Coils 4000 tons.
           \end{center}
           Given that there are 40 hours of production time available
           this week, the problem is to decide how many tons of bands
           and how many tons of coils should be produced to yield the
           greatest profit. Formulate this problem as a linear
           programming problem. Can you solve this problem by
           inspection?
           
           \item \points{40} A small airline, Ivy Air, flies between
           three cities: Ithaca (a small town in upstate New York),
           Newark (an eyesore in beautiful New Jersey), and Boston (a
           yuppie town in Massachusetts). They offer several flights
           but, for this problem, let us focus on the Friday afternoon
           flight that departs from Ithaca, stops in Newark, and
           continues to Boston. There are three types of passengers:
           \begin{enumerate}
               \item Those traveling from Ithaca to Newark (god only
               knows why).
               
               \item Those traveling from Newark to Boston (a very
               good idea).
               
               \item Those traveling from Ithaca to Boston (it depends
               on who you know).
           \end{enumerate}
           The aircraft is a small commuter plane that seats 30
           passengers. The airline offers three fare classes:
           \begin{enumerate}
               \item Y class: full coach.
               
               \item B class: nonrefundable.
               
               \item M class: nonrefundable, 3-week advanced purchase.
           \end{enumerate}
           Ticket prices, which are largely determined by external
           influences (i.e., competitors), have been set and
           advertised as follows:
           \begin{center}
               \begin{tabular}{l|rrr|}
                 & Ithaca-Newark & Newark-Boston & Ithaca-Boston\\
                 \hline
                 Y & 300 & 160 & 360\\
                 B & 220 & 130 & 280\\
                 M & 100 & 80  & 140\\
                 \hline
               \end{tabular}
           \end{center}
           Based on past experience, demand forecasters at Ivy Air
           have determined the following upper bounds on the number of
           potential customers in each of the 9 possible
           origin-destination/fare-class combinations:
           \begin{center}
               \begin{tabular}{l|rrr|}
                 & Ithaca-Newark & Newark-Boston & Ithaca-Boston\\
                 \hline
                 Y & 4 & 8 & 3\\
                 B & 8 & 13 & 10\\
                 M & 22 & 20  & 18\\
                 \hline
               \end{tabular}
           \end{center}
           The goal is to decide how many tickets from each of the 9
           origin/destination/fare-class combinations to sell.  The
           constraints are that the place cannot be overbooked on
           either the two legs of the flight and that the number of
           tickets made available cannot exceed the forecasted maximum
           demand. The objective is to maximize the revenue. Formulate
           this problem as a linear programming problem.
       \end{questions}
    }{}
    
    \item \HWProblem{100}%
    {Linear programming.}%
    {%
       Provide {\em detailed} solutions for the following problems,
       showing each pivoting stage separately.
       \begin{questions}[resume=LP]
           \item \points{15}\\
           maximize $6x_1 + 3x_2 + 5x_3 + 9x_4$\\
           subject to\\
           $2x_1 + x_2 + x_3 + 3x_4 \leq 5$\\
           $x_1 + 3x_2 + x_3 + 2x_4 \leq 3$\\
           $x_1, x_2, x_3, x_4 \geq 0$.
           
           \item \points{15}\\
           maximize $2x_1 + 4x_2$\\
           subject to\\
           $2x_1 + x_2 \leq 4$\\
           $2x_1 + 3x_2 \leq 3$\\
           $4x_1 + x_2 \leq 5$\\
           $x_1 + 5x_2 \leq 1$\\
           $x_1, x_2 \geq 0$.
           
       \end{questions}

       \Hr%

       \newcommand{\PathSet}{\EuScript{P}}%
       Consider a directed graph $\Graph$ with source vertex $s$ and
       target vertex $t$ and associated costs $\costX{\cdot}\geq 0$ on
       the edges. Let $\PathSet$ denote the set of all the directed
       (simple) paths from $s$ to $t$ in $\Graph$.
       
       Consider the following (very large) integer program:
       \begin{align*}
         \text{minimize}  ~~~& \sum_{e \in E(\Graph)} \costX{e} x_e  \\
         \text{subject to} ~~~& x_e \in \brc{0,1} \;\;\;\; \forall e \in
                                E(\Graph)\\
                             & \sum_{e \in \pi} x_e \geq 1 \;\;\;\;\; \forall \pi \in \PathSet.
       \end{align*}
       
       \begin{questions}[resume=LP]

           \item \points{10} What does this IP computes?
           
           \item \points{10} Write down the relaxation of this IP into
           a linear program.
           
           \item \points{10} Write down the dual of the LP from
           (B). What is the interpretation of this new LP? What is it
           computing for the graph $\Graph$ (prove your answer)?
           
           \item \points{10} The strong duality theorem states the
           following.
           
           \centerline{\fbox{
                 \begin{minipage}{0.8\linewidth}
                     \begin{theorem}
                         If the primal LP{} problem has an optimal
                         solution
                         $x^{*}=\pth{x_{1}^{*},\ldots,x_{n}^{*}}$ then
                         the dual also has an optimal solution,
                         $y^{*}=\pth{y_{1}^{*}, \ldots, y_{m}^{*}}$,
                         such that
                         \[
                             \sum_{j}c_{j} x_{j}^{*}=
                             \sum_{i}b_{i}y_{i}^{*}.
                         \]
                     \end{theorem}
                 \end{minipage}}}
           
           In the context of (C)-(E) what result is implied by this
           theorem if we apply it to the primal LP and its dual above?
           (For this, you can assume that the optimal solution to the
           LP of (B) is integral -- which is not quite true -- things
           are slightly more complicated than that.)
           
       \end{questions}

       \Hr%

       And now for something completely different.
       
       \begin{questions}[resume=LP]
           \item \itemlab{l:p:a}%
           \points{10} Given a weighted, directed graph
           $G = (V, E)$, with weight function
           $w : E \rightarrow \mathcal{R}$ mapping edges to
           real-valued weights, a source vertex $s$, and a destination
           vertex $t$. Show how to compute the value $d[t]$, which is
           the weight of a shortest path from $s$ to $t$, by linear
           programming.
           
           \item \points{10} Given a graph $G$ as in \itemref{l:p:a},
           write a linear program to compute $d[v]$, which is the
           shortest-path weight from $s$ to $v$, for each vertex
           $v \in V$.
           
           \item \points{10} In the {\em minimum-cost
              multicommodity-flow problem}, we are given a directed
           graph $G = (V, E)$, in which each edge $(u, v) \in E$ has a
           nonnegative capacity $c(u, v) \geq 0$ and a cost
           $\alpha(u, v)$. As in the multicommodity-flow problem
           (Chapter 29.2, CLRS), we are given $k$ different
           commodities, $K_1$, $K_2$, \ldots, $K_k$, where commodity
           $i$ is specified by the triple $K_i = (s_i, t_i,
           d_i)$. Here $s_i$ is the source of commodity $i$, $t_i$ is
           the sink of commodity $i$, and $d_i$ is the demand, which
           is the desired flow value for commodity $i$ from $s_i$ to
           $t_i$. We define a flow for commodity $i$, denoted by
           $f_i$, (so that $f_i(u, v)$ is the flow of commodity $i$
           from vertex $u$ to vertex $v$) to be a real-valued function
           that satisfies the flow-conservation, skew-symmetry, and
           capacity constraints. We now define $f(u, v)$ , the {\em
              aggregate flow}, to be sum of the various commodity
           flows, so that $f(u, v) = \sum_{i=1}^{k}f_i(u, v)$. The
           aggregate flow on edge $(u, v)$ must be no more than the
           capacity of edge $(u, v)$.
           
           The cost of a flow is
           $\sum_{u, v \in V} \alpha(u,v) f(u, v)$, and the goal is to
           find the feasible flow of minimum cost.  Express this
           problem as a linear program.
       \end{questions}
    }{}{}
    
\end{questions}

\end{document}

