%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{5}{May 15}{\bf May 22}

Note: the due date has been shifted due to Ditch Day.

Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}
\item Given a flow network with edge capacities $c(e)$, consider the following variants of the maximum flow problem. For each, formulate them as a linear program. 
\begin{enumerate}
\item We are interested in vertex-limited flow: for each vertex $v$ there is a limit $g(v)$, and we want the flow entering $v$ plus the flow exiting $v$ to not exceed $g(v)$. We are interested in the maximum $s$-$t$ flow subject to these additional constraints.

\item Multicommodity flow. There are $k$ pairs $s_i$ and $t_i$ and we want to pass at least $f_i$ units of flow from $s_i$ to $t_i$. Each of the $k$ flows should respect the conservation of flow constraints at each vertex, and the aggregate flow should not exceed the capacities $c(e)$. We are interested in whether such a multicommodity flow is feasible. 

\item There is a distinguished edge $e^*$ which is ``fragile''. We are interested in the maximum $s$-$t$ flow that minimizes the flow on edge $e^*$. That is, the flow value should achieve the maximum, but among all such flows, we want the one with the smallest flow across edge $e^*$.
\end{enumerate}

\item Total unimodularity. A matrix is said to be totally-unimodular if every submatrix (obtained by restricting to a subset of the rows and subset of the columns) has determinant $0$, $1$, or $-1$. The polytope $\{x : Ax = b, x \in R^n \geq 0\}$ has only integer vertices if $A$ is totally unimodular and $b$ is integer. 
\begin{enumerate}
\item Formulate Assignment Problem as a linear program in which you assume that the variables take on only integer values (this is called an integer linear program). Show that the constraint matrix is totally unimodular, and hence solving this linear program gives a legitimate solution to the Assignment Problem.
    
\item Suppose a car company has $m$ storage lots and $n$ retail showrooms, and it needs to ship cars from storage lots to showrooms. Each storage lot has a supply $a_i$ and each showroom has a demand $b_i$. We are also given costs $c_{i,j}$ between every storage lot and showroom. Shipping $x$ units from storage lot $i$ to showroom $j$ costs $c_{i,j}x$. You want to determine an optimal shipment scheme subject to the supply and demand constraints, that minimizes total cost. Formulate this as a linear program and then show that the constraint matrix is totally unimodular (so you are never asked to ship 2/3 of a car!)
    

\end{enumerate}
\item covering/packing LPs

\end{enumerate}
\end{document}
