\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}
\begin{center}
\textbf{\large
Fall 2013 \qquad Math 566 \qquad Implementation Assignment 3 
}
\end{center}

\vspace{1em}
\textbf{\large Problem: Maximum or Minimum Perfect Matchings in Bipartite Graphs}

In this report, you will implement the augmenting path algorithm for maximum matching in unweighted bipartite graphs and the Hungarian algorithm for maximum weighted perfect matchings in bipartite graphs.
As part of your implementation, you will also output the min-size vertex cover or the minimum-weight vertex cover for these problems.
You will also build a method for solving the minimum weight perfect matching problem for bipartite graphs, but you may simply program a reduction to the maximum weighted perfect matching problem.
(However, if you perform the reduction, you must still present a maximum-weight vertex under-cover for the proof by duality.)
While you may use a graph library such as the Sage Graph Library, you cannot use existing flow algorithms or use a linear programming solver.

%Remember, the point of this report is for you to explain your solution to the point that we can believe that you implemented the algorithm correctly. 
%So include as many details as you feel is appropriate, but do not simply paste code without a corresponding discussion that \emph{explains} that code.

\vspace{1em}
\textbf{\large Questions To Answer.} These questions should be answered within the body of your report. \emph{Do not simply answer these in separate items!}

\textbf{Q1.} Describe how you store the following items: (a) the current matching, (b) the current (weighted) vertex cover, and (c) the current excess matrix.

\textbf{Q2.} Describe your algorithm for finding an $M$-augmenting path in an unweighted bipartite graph.

\textbf{Q3.} How did you program the minimum-weight perfect matching problem? How did you solve the maximum weighted vertex under-cover problem? Give specific details!

\textbf{Q4.} What language, libraries, and environments did you use?

\textbf{Q5.} What challenges did you encounter during your implementation?

\textbf{Q6.} What online/library resources did you use?

\vspace{1em}

\small
\textbf{\large Problem Instances.}

\textbf{I1 \& I2.} Solve the maximum and minimum weighted perfect matching problems for the bipartite graphs given by the weight matrices below.
Present solutions to the corresponding dual problems as well.
These matrices are also given in CSV format in the files \texttt{match1.csv} and \texttt{match2.csv} on the course web page, and in Sage format in the files \texttt{match1.py} and \texttt{match2.py}.
\begin{center}
\begin{tabular}[h]{c@{\ }c}
$\left(\begin{array}{cccccccccc}
 1  &  0  &  7  &  4  &  9  &  6  &  3  &  9
&  4  &  0 \\
 6  &  4  &  7  &  1  &  6  &  7  &  7  &  6
&  7  &  5 \\
 2  &  7  &  6  &  9  &  6  &  1  &  2  &  2
&  0  &  2 \\
 9  &  0  &  7  &  1  &  5  &  0  &  7  &  4
&  8  &  4 \\
 4  &  1  &  9  &  2  &  0  &  8  &  8  &  8
&  2  &  9 \\
 1  &  4  &  3  &  3  &  3  &  4  &  0  &  3
&  5  &  9 \\
 2  &  6  &  7  &  7  &  0  &  6  &  7  &  8
&  1  &  9 \\
 9  &  2  &  6  &  8  &  1  &  3  &  2  &  1
&  9  &  4 \\
 1  &  1  &  9  &  1  &  8  &  2  &  8  &  1
&  7  &  8 \\
 9  &  0  &  8  &  2  &  7  &  2  &  4  &  5
&  8  &  0 
\end{array}\right)$
&
\footnotesize
$\left(\begin{array}{ccccccccccccccc}
13  & 13  & 18  & 10  &  7  &  3  &  1  &  5
&  4  &  8  & 10  &  6  &  4  & 10  &  4 \\
14  & 14  & 11  &  9  & 14  &  7  & 10  &  4
& 11  &  1  &  4  &  1  &  2  &  4  & 11 \\
16  & 14  & 17  &  8  & 10  & 18  &  0  &  6
& 16  & 14  & 14  & 12  & 17  &  9  & 15 \\
 0  & 16  & 18  &  7  &  1  & 18  & 11  &  1
&  6  &  1  &  3  &  8  & 17  &  2  & 19 \\
14  &  6  & 18  & 11  & 19  &  9  &  0  & 16
& 16  & 12  & 18  &  7  &  2  &  3  & 12 \\
17  &  6  &  6  & 14  &  3  & 15  & 18  &  1
&  4  &  5  &  2  &  2  &  2  & 16  & 18 \\
 1  &  9  & 10  & 13  &  3  & 12  &  1  &  6
&  8  & 14  &  3  & 19  & 18  &  1  &  2 \\
12  &  9  &  2  & 11  &  4  &  1  & 11  & 16
&  1  &  2  & 17  &  8  &  1  & 14  &  1 \\
19  & 15  &  6  &  8  &  4  &  5  &  2  &  4
&  9  &  7  &  5  & 11  &  3  &  5  & 12 \\
14  & 14  & 16  &  8  & 17  &  5  & 17  & 16
&  7  &  1  &  5  & 17  &  8  &  9  &  6 \\
 1  &  5  &  4  &  5  & 17  & 17  & 15  & 16
& 17  & 19  & 17  &  7  &  5  &  1  & 18 \\
12  &  6  &  3  & 15  &  2  & 15  &  5  & 19
&  8  &  5  &  4  &  8  &  5  & 16  & 19 \\
 0  &  8  & 13  & 17  & 11  &  6  & 16  & 11
&  7  & 10  & 18  &  5  &  1  & 17  &  4 \\
 6  & 11  & 12  & 16  &  9  & 15  &  3  & 11
&  9  &  9  & 11  &  5  & 18  &  7  &  4 \\
12  & 18  & 12  &  5  & 11  &  3  & 19  & 11
&  3  & 13  &  1  & 17  &  6  &  4  & 10 
\end{array}\right)$
\\
\textbf{I1.}
&
\textbf{I2.}
\end{tabular}
\end{center}
 
\textbf{I3 \& I4.} See the files \texttt{match3.csv} and \texttt{match4.csv} (or \texttt{match3.py} and \texttt{match4.py} for Sage format) on the course web page and solve the instances of maximum- and minimum-weight perfect matchings. 
Present solutions to the corresponding dual solutions as well.
\end{document} 