\begin{titlepage}
\vspace*{.25in}

%% This is the title
{\LARGE \bf
\begin{center}
The Assignment Problem \\
on Parallel Architectures
\end{center}
}

%% Now for the authors and the affiliations
{\large

\begin{center}
  {\bf Martin L. Brady}  \\
  Dept. of Electrical and Computer Engineering, \\
  Pennsylvania State University, \\
  University Park, PA 16802
\end{center}

\begin{center}
  {\bf Ken K. Jung}, {\bf Mark V. LaPolla}, \\
  {\bf H.T. Nguyen}, {\bf and Raghu Raghavan}\footnote{Current Address: Institute of System Science, National University of Singapore, Kent Ridge, Singapore 0511} \\
  Advanced Computing Laboratory \\
  Lockheed Research and Development Division \\
  Palo Alto, CA   94304
\end{center}

\begin{center}
  {\bf Ramesh Subramonian} \\
  Division of Computer Science, \\
  University of California, \\
  Berkeley, CA 94720 
\end{center}
}

\vspace*{.25in}

{\small

\begin{center} {\bf Abstract} \end{center}
Implementation results are presented for new algorithms that solve 
the Assignment or minimum-weight bipartite matching problem in parallel 
on regular SIMD (Single-Instruction Multiple-Data) architectures.  
In particular, we are concerned with the implementation on simple 
bit-serial massively parallel arrays of processing elements (PE).  
For the Assignment problem, we have found several parallel algorithms that 
are good from both a theoretical and a practical point of view.  We 
evaluate parallel implementations of three different algorithms.  
The first implementation is that of an early algorithm which was perhaps the 
first SIMD implementation described for Assignment.  The second is 
more recent, and takes advantage of recent theoretical work on 
the problem for the PRAM model.  Finally, as a result of discussions at 
the DIMACS workshop, we have implemented the Auction algorithm on 
a shared-memory multiprocessor, on SIMD machines, and on a distributed
network of workstations.  
}

\end{titlepage}