% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{kbordermatrix,blkarray}
\usepackage[ruled,linesnumbered,vlined]{algorithm2e} 
\pagestyle{plain}

\bibliographystyle{unsrt}   %>>>> makes bibtex use spiebib.bst

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

%\def\comment#1{$\Rightarrow${\small\em #1}}
\def\comment#1{}
\newenvironment{chapterquote}
  {\begin{quotation}
      \sf}
  {\end{quotation}}
\def\cq#1#2{\begin{chapterquote}#1\flushright\textbf{#2}\end{chapterquote}}


\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\SetAlgoCaptionSeparator{.5}


\begin{document}
\title{Minimum Cost Perfect Matching
}
\maketitle
\begin{abstract}
  This is pseudocode for the Hungarian Algorithm for Minimum Cost
  Perfect Matching in Bipartite Graphs, adapted from the paperback
  edition of \emph{A Gentle Introduction to Optimization}, B. Guerin
  \emph{et al.}  This finds subgraphs of the original bipartite graph
  (which is often a complete bipartite graph), and uses the Perfect
  Matching algorithm as a subroutine to figure out if there is a
  perfect matching, in which case we are done.
\end{abstract}

$N_H(S)$ is the set of neighbors of the set $S$ on the graph $H$.  One
thing I do not like about this particular pseudocode is that the
interface with the perfect matching subroutine is imprecise, and this
algorithm depends on side effects from that subroutine.  The
subroutine might return (a) a new (larger) matching $M$, (b) a new
(larger) tree $T$, or (c) a deficient set for that particular graph
$H$.

\begin{algorithm}
\setcounter{algocf}{2}
\caption{Minimum cost perfect matching in bipartite graphs (fast version)}
\label{algo3}

\AlgoDisplayBlockMarkers\AlgoDisplayGroupMarkers\SetAlgoBlockMarkers{ \{}{ \}\ }%
\SetAlgoNoEnd\SetAlgoNoLine

\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}%
\SetKwRepeat{Do}{do}{While}%
\Input{Bipartite graph $G=(V,E)$ with bipartition $U,W$ where
  $ |U| = |W| \geq 1$}
\Output{A minimum cost perfect matching $M$ or a deficient set $S$}
$M := \varnothing$ \\
$T := (\{r\},\varnothing)$ where $r\in U$ is any $M$-exposed vertex \\
$\vec{y_v}:=\frac{1}{2}\operatorname{min}\left\{c_e : e \in E\right\}\text{, for all } v \in V$

\While{(1)}{
Construct graph $H$ (a subset of the original graph $G$) \\
with vertices $V$ and edges \{$uv$ $\in$ $E$ : $c_{uv}$ = $\vec{y_u}$ + $\vec{y_v}\}$\\
Invoke the subroutine (Algo. 3.4) with $H$,$M$, and $T$

	\uIf{outcome (a) of subroutine occurs}
	{
		\uIf{$M$ is a perfect matching of $H$}{
			\textbf{stop} ($M$ is minimum cost perfect matching of $G$)
		}
	} \ElseIf{outcome (c) of subroutine occurs}{
			Let $S := B(T)$\\
			\lIf{all edges of $G$ with an endpoint in $S$ have an endpoint in $N_H(S)$} {
				\textbf{stop} ($G$ has no perfect matching)
			}
                        Otherwise, adjust the costs to create a new
                        zero, and loop
                        $\epsilon = \operatorname{min}\{c_{uv} - \vec{y_u} - \vec{y_v} : u \in S, v \notin V(T)\}$
		
		\begin{equation}
		\vec{y_v}:= \left\{
			\begin{array}{lr}
			    \vec{y_v}+\epsilon \text{ for } v \in S\\
			    \vec{y_v}-\epsilon \text{ for } v \in N_H(S) \\
			    \vec{y_v} \text{ otherwise }
			  \end{array}
			\right.
		\end{equation}

	} \ElseIf{outcome (b) of subroutine occurs}{
          Just loop again with augmented path
	}
}
\end{algorithm}

\end{document}
