\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb}
\usepackage{hyperref}
\usepackage{boxedminipage}
\usepackage{bm}
%\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, Spring 2018}
\\[0.5ex]
\textbf{HW 9 (due Wednesday, April 18th 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
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
\bigskip
%
%\hrule
%\medskip\noindent
%For problems that ask to prove that a given problem $X$ is NP-hard, a full-credit solution requires the following components:
%\begin{itemize}\itemsep0pt
%\item
%Specify a known {NP}-hard problem $Y$, taken from the problems listed in the notes.
%\item
%Describe a polynomial-time algorithm for $Y$, using a black-box polynomial-time algorithm for $X$ as a subroutine. Most {NP}-hardness reductions have the following form: Given an arbitrary instance of $Y$, describe how to transform it into an instance of $X$, pass this instance to a black-box algorithm for $X$, and finally, describe how to transform the output of the black-box subroutine to the final output. A cartoon with boxes may be helpful.
%\item
%Prove that your reduction is correct. As usual, correctness proofs for {NP}-hardness reductions usually have two components (“one for each f”).
%\end{itemize}
%\hrule
%\bigskip
%
\newpage
\begin{enumerate}
%----------------------------------------------------------------------
%%% Problem 1
\item You are given the following linear program
\begin{align*}
\begin{array}{ll}
max \quad & \displaystyle{10 x_1 + 5 x_2 + 7.5 x_3} \\
s.t. & 6 x_1 + 4 x_2 + 10 x_3 \leq 55 \\
& 2 x_1 + x_2 + x_3 \leq 13 \\
& x_1 + x_2 + 3 x_3 \leq 15 \\
& 10 x_1 + 4 x_2 + 8 x_3 \leq 57 \\
& x_1, x_2, x_3 \geq 0
\end{array}
\end{align*}
Note that $(0,0,0)$ is a feasible vertex of in the above LP.
Run the Simplex algorithm on the above program to calculate its solution. Write the sequence
of vertices visited by the Simplex algorithm, and what inequalities are tight at each step.
%%% Problem 2
\item Let $G = (V_1 \cup V_2, E)$ be a bipartite graph.
\begin{enumerate}
\item Write a linear program for the maximum matching problem in $G$.
\item Write the dual program of the above primal program. Can you interpret its solution?
What do the dual variables represent?
\end{enumerate}
%%% Problem 3
\item You are given the following linear program
\begin{align*}
\begin{array}{ll}
max \quad & \displaystyle{\bm{c}^T \bm{x}} \\
s.t. & \displaystyle{A \bm{x} \leq \bm{b}} \\
& \bm{x} \geq 0
\end{array}
\end{align*}
and you know that there exists an $\bm{x}$ that is a feasible solution to the above program.
Furthermore, you know that the dual of this program also has a $\bm{y}$ that is a feasible
solution.
\begin{enumerate}
\item Write the dual program to the above primal program.
\item Design a single \textit{linear feasibility formulation} that exactly captures all
the {\em optimal solutions} of both primal and the dual. Show that $(x^*,y^*)$ is feasible in
your formulation if and only if $x^*$ is an optimal solution of the primal and $y^*$ is an optimal solution of the dual.
\end{enumerate}
%\item %Construct an ILP where the variables are not obvious.
\end{enumerate}
\newpage
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item Suppose we have a linear program $\max c x, A_1x \le b_1, A_2x=b_2, A_3x \ge b_3, x\ge 0$. What is its dual?
\item See Problem 3 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}
\item See HW 8 from Sariel's course in Fall 2015.
\url{https://courses.engr.illinois.edu/cs473/fa2015/w/hw/hw_08.pdf}.
\end{itemize}
\end{document}