\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{Thu., Oct. 31, 2019}}{\parbox{2in}{Prof.\ Michael A. Forbes\\ Prof.\ Chandra Chekuri}}{Due: \textit{Thu., Nov. 7, 2019 (10:00am)}}{Problem Set \#8}
\bigskip
\hrule
\bigskip
For problems that use maximum flows as a black box, a full-credit solution requires the following.
\begin{itemize}
\item A complete description of the relevant flow network, specifying the set of vertices, the set of edges (being careful about direction), the source and target vertices $s$ and $t$, and the capacity of every edge. (If the flow network is part of the original input, just say that.)
\item A description of the algorithm to construct this flow network from the stated input. This could be as simple as ``we can construct the flow network in $O(n^3)$ time by brute force.''
\item A description of the algorithm to extract the answer to the stated problem from the maximum flow. This could be as simple as ``return \textsc{True} if the maximum flow value is at least $42$ and \textsc{False} otherwise.''
\item A proof that your reduction is correct. This proof will almost always have two components. For example, if your algorithm returns a boolean value, you should prove that its \textsc{True} answers are correct and that its \textsc{False} answers are correct. If your algorithm returns a number, you should prove that number is neither too large nor too small.
\item The running time of the overall algorithm, expressed as a function of the original input parameters, not just the number of vertices and edges in your flow network.
\item You may assume that maximum flows can be computed in $O(VE)$ time. Do \emph{not} regurgitate the maximum flow algorithm itself.
\end{itemize}
Reductions to other flow-based algorithms described in class or in the notes (for example: edge-disjoint paths, maximum bipartite matching, minimum-cost max-flows) or to other standard graph problems (for example: reachability, minimum spanning tree, shortest paths) have similar requirements.
\bigskip
\hrule
\bigskip
All (non-optional) problems are of equal value.
\begin{enumerate}
\item Let $G=(L\sqcup R,E)$ be a $d$-regular undirected bipartite graph (each node has degree exactly $d$), and where each part has size $|L|=|R|=n$.
\begin{enumerate}
\item Prove that $G$ has a perfect matching via two methods.
\begin{enumerate}
\item Use Hall's theorem.
\item Exhibit a feasible fractional flow in an appropriate network, which implies a matching of size $n$ in $G$.
\end{enumerate}
\item Using the previous part, prove that the edges of $G$ can be partitioned into $d$ perfect matchings, and hence the edges of $G$ can be colored with $d$ colors such that no two adjacent edges (edges that share a vertex) have the same color --- this is called an \emph{edge coloring}.
\item Use the previous part to show that a bipartite graph with maximum degree $d$ (not necessarily regular) has an edge coloring with at most $d$ colors.
\end{enumerate}
\item Let $G=(V,E)$ be a graph with edge weights given by $c:E \to \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 matching problem the input is a graph $G=(V,E)$ and \emph{non-negative} weights $w:E\to \mathbb{R}_{\ge 0}$, 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, that is, may not be a perfect matching. Describe an efficient reduction from min-cost perfect matching to max-weight matching.
\emph{Note:} Your reduction must work even when $G$ is not bipartite.
\item Given points $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ in the plane the \emph{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{enumerate}
\item The $L_{\infty}$ error of the line $y=ax+b$ is defined by
\[
\eps_{\infty}(a,b)=\max_{i=1}^n |y_i-(ax_i+b)|
\;.
\]
Describe a linear program whose solution describes a line with the minimum $L_{\infty}$ error.
\item The $L_1$ error of the line $y=ax+b$ is defined by
\[
\eps_1(a,b)=\sum_{i=1}^n |y_i-(ax_i+b)|
\;.
\]
Describe a linear program whose solution describes a line with the minimum $L_1$ error.
\end{enumerate}
\textit{Note:} 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 (\textbf{optional}, \emph{not} for submission) Let $G=(V,E)$ be a flow network with integer edge capacities. An edge $e$ is called \emph{critical} if $e$ is in every minimum $(s,t)$-cut. Describe an efficient algorithm that checks whether a given edge $e$ is critical or not.
\end{enumerate}
\end{document}