\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 9 (due Tuesday, November 15 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}
%----------------------------------------------------------------------
\item Given points $(x_1,y_1), (x_2,y_2),\ldots, (x_n,y_n)$ in the
plane the {\em linear regression problem} asks for real numbers $a$ and
$b$ such that the line $y = ax + b$ fits the points as closely as possible
according to some criterion. The most common fit criterion is minimizing
the $L_2$ error, defined as follows:
$$\eps_2(a,b) = \sum_{i=1}^n (y_i - ax_i - b_i)^2.$$
But there are several other fit criteria, some of which can be optimized
by linear programming.
\begin{itemize}
\item The $L_1$ error of the line $y = ax + b$ is defined as follows
$$\eps_1(a,b) = \sum_{i=1}^n |y_i - ax_i - b|.$$
Describe a linear program whose solution $(a,b)$ describes the line with
the minimum $L_1$ error.
\item The $L_{\infty}$ error of the line $y = ax + b$ is defined as follows.
$$\eps_{\infty}(a,b) = \max_{i=1}^n |y_i - ax_i - b|.$$
Describe a linear program whose solution $(a,b)$ describes the line with
the minimum $L_{\infty}$ error.
\end{itemize}
{\bf Comment:} In general the points can be in $\mathbb{R}^d$ for some $d$
and in that case one fits a hyperplane. We are here considering the simple
case of $d=2$.
\item The facility location problem is the following. There is a set
of $n$ facilities $F$ and $m$ clients $C$. The cost of openining a
facility $i$ is $f_i$. There is a cost $c(i,j)$ to connect client
$j$ to facility $i$. The goal is to open a susbet of the facilities
and connect each client to an open facility. The objective function
is to minimize the sum of the facility opening costs and the
connection costs. Write an integer linear programming formulation
for this problem using two sets of decision variables, one set for
opening facilities, and one set for assigning clients to open
facilities. Prove that it is sufficient to constrain only the
facility opening variables to be integer valued. Such a problem is
called a mixed-integer programming problem.
\item A directed graph $G=(V,E)$ is {\em strongly
connected} if for all $u,v \in V$ there is a path in $G$ from
$u$ to $v$ and from $v$ to $u$. The {\sc Strongly-Connected
Spanning Subgraph} problem is the following: given a directed
graph $G=(V,E)$ and an integer $k$ is there a spanning subgraph
$H$ of $G$ with at most $k$ edges such that $H$ is strongly
connected? A subgraph is spanning if it contains all the vertices of
the original graph. Describe a reduction to show that {\sc
Strongly-Connected Spanning Subgraph} is NP-Complete.
\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}