%  Problem set 5
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\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
