\documentclass[11pt]{article}

%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}

%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}

\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\epsilon}

\begin{document}
\setlength{\parskip}{.1 in}

\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Fall 2016}
\\[0.5ex]
\textbf{HW 8 (due Tuesday, November 1st at 8pm)}
\end{center}

\noindent
This homework contains three problems. {\bf Read the instructions for
  submitting homework on the course webpage}. 

\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with up to three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.

\bigskip
\hrule
\medskip\noindent
You may assume the following results in your solutions:
\begin{itemize}\itemsep0pt
\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 \textbf{\textit{not}} necessary to express the linear program in canonical form, or even in matrix form.  Clarity is much more important than formality.
\medskip
\hrule
\noindent
For reductions to flow-based algorithms described in class or in the notes (for example: edge-
disjoint paths, maximum bipartite matching, minimum-cost circulation) or to other standard graph
problems (for example: reachability, minimum spanning tree, shortest paths), see HW 7.
\medskip
\hrule
\bigskip

\newpage

\begin{enumerate}
%----------------------------------------------------------------------
\item Suppose we are given an $n\times n$ grid, some of whose cells
  are marked; the grid is represented by an array $M[1 .. n,1 .. n]$
  of booleans, where $M[i, j] = \text{True}$ if and only if cell $(i, j)$ is
  marked. A monotone path through the grid starts at the top-left
  cell, moves only right or down at each step, and ends at the
  bottom-right cell. Our goal is to cover the marked cells with as few
  monotone paths as possible. 

  \begin{figure}[h]
    \centering
    \includegraphics[width=5in]{monotone-paths.pdf}
  \end{figure}

  \begin{itemize}
  \item {\bf Not to submit:} 
    Describe an algorithm to find a monotone path that covers the 
    largest number of marked cells.
  \item {\bf Not to submit:} There is a natural greedy heuristic to
    find a small cover by monotone paths: If there are any marked
    cells, find a monotone path $\Pi$ that covers the largest number of
    marked cells, unmark any marked cells covered by $\Pi$,
    and recurse. Show that this algorithm does {\em not} always compute an
    optimal solution.
  \item Describe and analyze an efficient algorithm to compute the
    smallest set of monotone paths that covers every marked cell.
  \end{itemize}

\item Let $G=(V,E)$ be a graph with edge weights given by $c: E
  \rightarrow \mathbb{R}$. In the min-cost perfect matching problem
  the goal is to find a minimum cost perfect matching $M$ in $G$ (if
  there is one, otherwise the algorithm has to report that there is
  none) where the cost of a matching $M$ is $\sum_{e \in M} c(e)$;
  note that the costs can be negative. In the maximum weight perfect
  matching problem the input is a graph $G=(V,E)$ and {\em non-negative}
  weights $w: E \rightarrow \mathbb{R}_+$ and the goal is to find a
  matching $M$ of maximum weight. Note that a maximum weight matching
  may not be a maximum cardinality matching. Describe an efficient 
  reduction from min-cost perfect matching to max-weight matching.

\item Consider a polyhedron $P$ in $n$ dimensions defined by a set of
  $m$ inequalities $Ax \le b$. Let $z \in \mathbb{R}^n$ be a point.
  Describe a polynomial-time algorithm to check whether $z$ is a
  basic feasible solution of $P$.
\end{enumerate}

\vspace{0.5in}

{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}

\begin{itemize}
\item See Problems 1 and 2 in HW 8 from Jeff's home work
last spring. \url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw8.pdf}

\item See HW 5 from Chandra's graduate algorithms course in Fall 2011.
\url{https://courses.engr.illinois.edu/cs573/fa2011/Homework/hw5.pdf}

\end{itemize}
\end{document}

