\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts, amsmath, amssymb, amsthm}
\usepackage{microtype}
\usepackage{nicefrac}
\usepackage[small]{complexity}
\renewcommand{\S}{\defaultS}
\renewcommand{\L}{\ComplexityFont{L}}
\newcommand{\ETIME}{\ComplexityFont{E}}
\usepackage[colorlinks=true]{hyperref}
\hypersetup{
linkcolor=[rgb]{0.5, 0.2, 0.2},
citecolor=[rgb]{0.2, 0.5, 0.2},
urlcolor =[rgb]{0.2, 0.2, 0.5}
}
\newcommand{\thecourse}{cs473: Algorithms}
\newcommand{\handout}[5]{
%\renewcommand{\thepage}{#1-\arabic{page}}
\noindent%
\begin{center}%
\framebox{%
\vbox{%
\vspace{1mm}%
\hbox to 5.78in { {\bf \thecourse} \hfill #2 }%
\vspace{4mm}%
\hbox to 5.78in { {\Large \hfill #5 \hfill} }%
\vspace{4mm}%
\hbox to 5.78in { {#3 \hfill #4} }%
}%
}%
\end{center}%
\vspace*{4mm}%
}%
\setlength\parindent{0pt}
% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
\newif\ifstaritem
\newcommand{\setupstarnumerate}{%
\global\staritemfalse
\let\origmakelabel\makelabel
\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
\def\makelabel##1{%
\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
\global\staritemfalse}%
}
% math
\newcommand{\N}{\mathbb{N}}
\newcommand{\bits}{\ensuremath{\{0,1\}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\rX}{\mathsf{X}}
\newcommand{\rY}{\mathsf{Y}}
\newcommand{\rZ}{\mathsf{Z}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\vec}[1]{\overline{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\eps}{\epsilon}
\renewcommand{\E}{\mathbb{E}}
% copied from 2018-01_cs473-algorithms.lectures.zip/prefix.tex
\newcommand{\fcode}[1]
{
\smallskip
\centerline{
\fbox{
\begin{minipage}{0.95\linewidth}
\code{#1}
\end{minipage}
}
}
\smallskip
}
\newcommand{\innercode}[1]
{
\begin{tabbing}
----\=----\=----\=----\=----\=----\=----\kill
#1
\end{tabbing}
}
\newcommand{\code}[1]
{
\footnotesize
\tt
\begin{center}
\innercode{#1}
\end{center}
}
\begin{document}
\handout{0}{Assigned: \textit{Wed., Nov. 13, 2019}}{\parbox{2in}{Prof.\ Michael A. Forbes\\ Prof.\ Chandra Chekuri}}{Due: \textit{Wed., Nov. 20, 2019 (10:00am)}}{Problem Set \#9}
\bigskip
\hrule
\bigskip
For problems that ask for a linear-programming formulation of some problem, a full-credit solution requires the following components:
\begin{itemize}
\item A list of variables, along with a brief in-words description of what each variable represents.
\item A linear objective function (expressed either as minimization or maximization, whichever is more appropriate), along with a brief in-words description of its meaning.
\item A sequence of linear inequalities (expressed using $\le$, $=$, or $\ge$, whichever is more appropriate), along with a brief in-words description of what each constraint represents.
\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.
\bigskip
\hrule
\bigskip
All (non-optional) problems are of equal value.
\begin{enumerate}
\item Consider the following scheduling problem. There are $n$ jobs that need to be scheduled on $m$ identical machines, where each job takes one unit of time to complete. Each job $j$ has a release time $r_j$ and a deadline $d_j$ both of which are integers. A schedule assigns each job to a time slot $[t,t+1]$ for some integer $t$ and to some machine such that no two jobs are assigned to the same slot on the same machine. If job $j$ is completed by its deadline there is no penalty; if it completes at time $C_j>d_j$ then it incurs a penalty of $C_j-d_j$. A job cannot be scheduled before it is release time. The goal is find a schedule for all of the jobs on the given machines so as to minimize the total penalty.
Describe a polynomial time algorithm for this problem via reduction to minimum-cost max-flow. Be sure to pay attention to the fact that your algorithm runs in polynomial time by examining carefully the size of the input.
\item Flows are typically defined as a function on the edges, but the path-based definition is useful and necessary in various applications. Let $G=(V,E)$ be a directed graph with non-negative capacities $c:E\to\mathbb{R}_{\ge0}$. Given distinct nodes $s,t\in V$ let $P_{s,t}$ denote the set of all simple paths between $s$ and $t$.
\begin{enumerate}
\item Write the maximum $(s,t)$-flow problem as a linear programming problem with one variable for each path $p\in P_{s,t}$. Note that the primal can have an exponential (in $|V|$) number of variables. Write its dual.
\item Suppose we are given an assignment of values to the variables in the dual. Show that, even though there are possibly exponentially-many constraints, one can use a shortest path algorithm to efficiently check that the values satisfy all the constraints of the dual.
\end{enumerate}
\item The facility location problem is the following. There is a set of $n$ facilities $F$ and $m$ clients $C$. The cost of opening 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 subset 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 linear programming problem.
\end{enumerate}
\end{document}