% Problem set 5
% Combinatorial Optimization, SUAMI, summer 2015
% Brian Kell
\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein
% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
\setbox0=\hbox{\fig{#1}}%
\dimen0=0.5\ht0%
\advance\dimen0 by-0.3\ht\strutbox
\lower\dimen0\box0%
}}
% AMSFonts
\input amssym.tex
\font\titlefont=cmbx12 \font\smfont=cmr8 \font\transposefont=cmss8 at6pt
\headline={\hfil}
\footline={\hfil}
\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}
\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|} \def\rabs{\mathclose|} \def\abs#1{\labs#1\rabs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~5}
\smallskip
\centerline{Assigned Monday, June~15, 2015. Due Thursday, June~18, 2015.}
\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Consider the problem of determining the least expensive way to
complete a project by a given deadline (as we studied last week). When the
linear program is formulated, the objective function has a constant term. For
instance, if activities A,~B, and~C have usual times of 8,~5, and 7~days
and can be sped up at a cost of \$200,~\$150, and \$225 per day, respectively,
then the objective function (i.e., the total speedup cost) is
$$200(8-d_{\rm A})+150(5-d_{\rm B})+225(7-d_{\rm C}),$$
where $d_{\rm A}$,~$d_{\rm B}$, and~$d_{\rm C}$ are duration variables for the
three activities. When expanded, this objective function becomes
$$3925-200d_{\rm A}-150d_{\rm B}-225d_{\rm C},$$
which has the constant term~3925. Describe a way to handle an objective
function with a constant term in the simplex algorithm.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem What is the greatest possible number of critical paths in a project
with $n$~activities? Describe a family of examples for infinitely many values
of~$n$ that attain this number of critical paths.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Consider a directed graph~$G=(V,E)$ with nonnegative edge weights
$c_{ij}\ge0$ and specified nodes $s,t\in V$. For each node $i\in V$, let
$\pi_i$ be the distance of a shortest (directed) path from $i$ to~$t$. (Assume
that every node~$i$ has such a path to~$t$.) Show that $\pi$ is an optimal
feasible solution to the dual of the node-arc LP formulation for the shortest
path problem on~$G$ from $s$ to~$t$. Is the assumption $c_{ij}\ge0$ necessary?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Use Dijkstra's algorithm (or the primal-dual algorithm) to find a
shortest path from $s$ to~$t$ in the following undirected graph. [The first
question to consider is how to use one of these algorithms to find a shortest
path in an {\it undirected\/} graph.]
$$\fig{pset05-4.mps}$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Give an example of a simple graph with at least two vertices such that
no two vertices have the same degree, or explain why this is impossible.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Let $G=(V,E)$ be a simple undirected graph, and let $n=\abs V$. Prove
that all of the following statements are equivalent.
\smallskip
\item{(a)} $G$~is a tree (that~is, $G$~is connected and acyclic).
\smallskip
\item{(b)} For any two distinct vertices $u,v\in V$, there exists a unique
path in~$G$ between $u$~and~$v$.
\smallskip
\item{(c)} $G$~is minimally connected: $G$~is connected, but if any edge is
removed from~$G$ then the resulting graph is disconnected.
\smallskip
\item{(d)} $G$~is maximally acyclic: $G$~is acyclic, but if any edge is added
joining nonadjacent vertices of~$G$ then the resulting graph has a cycle.
\smallskip
\item{(e)} $G$~is connected and has $n-1$ edges.
\smallskip
\item{(f)} $G$~is acyclic and has $n-1$ edges.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bye