% ---------
% Compile with “pdflatex hw0”.
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage[mathletters]{ucs} % define text Greek letters; load BEFORE inputenc
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{fourier-orns}
\usepackage{eucal}
\usepackage{enumerate}
\usepackage{stmaryrd}
\hidesolutions
% ======================================================
\begin{document}
\headers{CS 473}{Homework 8 (due April 12)}{Spring 2016}
\thispagestyle{empty}
\begin{center}
\Large\textbf{CS 473 \,\decosix\, Spring 2016}%
\\
\Large \textbf{\decothreeleft~ Homework 8 ~\decothreeright}
\\[0.5ex]
\large Due Tuesday, April 12, 2016, at 8pm
\end{center}
\hrule
\medskip\noindent
You may assume the following results in your solutions:
\begin{itemize}\cramped
\item
Maximum flows and minimum cuts can be computed in $O(VE)$ time.
\item
Minimum-cost flows can be computed in $O(E^2 \log^2 V)$ time.
\item
Linear programming problems with integer coefficients can be solved in polynomial time.
\end{itemize}
\medskip
\hrule
\medskip
For problems that ask for a linear-programming formulation of some problem, a full credit solution requires the following components:
\begin{itemize}\itemsep0pt
\item
A list of variables, along with a brief English description of each variable. (Omitting these English descriptions is a Deadly Sin.)
\item
A linear objective function (expressed either as minimization or maximization, whichever is more convenient), along with a brief English description of its meaning.
\item
A sequence of linear inequalities (expressed using $\le$, $=$, or $\ge$, whichever is more appropriate or convenient), along with a brief English description of each constraint.
\item
A proof that your linear programming formulation is correct, meaning that the optimal solution to the original problem can always be obtained from the optimal solution to the linear program. This may be very short.
\end{itemize}
It is \EMPH{not} necessary to express the linear program in canonical form, or even in matrix form. Clarity is much more important than formality.
\medskip
\hrule
\bigskip
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.1fil
%----------------------------------------------------------------------
\item
Suppose your are given a rooted tree $T$, where every edge $e$ has two associated values: a non-negative \emph{length} $\ell(e)$, and a \emph{cost} $\$(e)$ (which could be positive, negative, or zero). Your goal is to add a non-negative \emph{stretch} $s(e) \ge 0$ to the length of every edge $e$ in $T$, subject to the following conditions:
\begin{itemize}
\item
Every root-to-leaf path $\pi$ in $T$ has the same total stretched length $\sum_{e\in \pi} (\ell(e) + s(e))$
\item
The total \emph{weighted} stretch $\sum_e s(e) \cdot \$(e)$ is as small as possible.
\end{itemize}
\begin{center}
\includegraphics[scale=0.375]{Fig/tree-stretch}
\end{center}
\begin{enumerate}
\item
Describe an instance of this problem with no optimal solution.
\item
Give a concise linear programming formulation of this problem. (For the instance described in part (a), your linear program will be unbounded.)
\item
Suppose that for the given tree $T$ and the given lengths and costs, the optimal solution to this problem is unique. Prove that in this optimal solution, we have $s(e)=0$ for every edge on some longest root-to-leaf path in $T$. In other words, prove that the optimally stretched tree with the same depth as the input tree. \Hint{What is a basis in your linear program? What is a \textbf{feasible} basis?}
\end{enumerate}
\textcolor{Red}{Problem 1(c) originally omitted the uniqueness assumption and asked for a proof that \EMPH{every} optimal solution has an unstretched root-to-leaf path, but that more general claim is false. For example, if every edge has cost zero, there are optimal solutions in which every edge has positive stretch.}
%\item
%Describe and analyze an algorithm that solves this problem in $O(n)$ time. Your algorithm should either compute the minimum total weighted stretch, or report correctly that the total weighted stretch can be made arbitrarily negative.
\bigskip
\item
Describe and analyze an efficient algorithm for the following problem, first posed and solved by the German mathematician Carl Jacobi in the early 1800s.\footnote{Carl Gustav Jacob Jacobi. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque. \emph{J. Reine Angew. Math.} 64(4):297--320, 1865. Posthumously published by Carl Borchardt.}
\begin{quote}\small\itshape
Disponantur $nn$ quantitates $h^{(i)}_k$ quaecunque in schema Quadrati, ita ut $k$
habeantur $n$ series horizontales et $n$ series verticales, quarum quaeque est $n$ terminorum. Ex illis quantitatibus eligantur $n$ transversales, i.e. in seriebus horizontalibus simul atque verticalibus diversis positae, quod fieri potest $1. 2 \dots n$ modis; ex omnibus illis modis quaerendum est is, qui summam $n$ numerorum electorum suppeditet maximam.
\end{quote}
For those few students who are not fluent in mid-19th century academic Latin, here is a modern English translation of Jacobi’s problem. Suppose we are given an $n\times n$ matrix~$M$. Describe and analyze an algorithm that computes a permutation~$\sigma$ that maximizes the sum $\sum_{i=1}^n M_{i, \sigma(i)}$, or equivalently, permutes the columns of $M$ so that the sum of the elements along the diagonal is as large as possible.
Please do not submit your solution in mid-19th century academic Latin.
\bigskip
\item
Suppose we are given a sequence of $n$ linear inequalities of the form $a_i x + b_i y \le c_i$. Collectively, these $n$ inequalities describe a convex polygon $P$ in the plane.
\begin{enumerate}
\item
Describe a linear program whose solution describes the largest square with horizontal and vertical sides that lies entirely inside $P$.
\item
Describe a linear program whose solution describes the largest circle that lies entirely inside $P$.
\end{enumerate}
\begin{center}
\includegraphics[scale=0.3]{../notes/Fig/polyhedron-square}\qquad
\includegraphics[scale=0.3]{../notes/Fig/polyhedron-circle}\\
\end{center}
\end{enumerate}
\end{document}