\section{Introduction}
\label{intro}
The Assignment problem is a classic combinatorial optimization
problem. Its practical importance has resulted in a lot of theoretical
algorithms and practical implementations.

We have found several parallel algorithms that run efficiently on SIMD
machines and are good from both a theoretical and a practical point of
view.
SIMD machines consisting of many simple processors interconnected in
a scaleable and regular manner have become commercially widespread.
How restrictive this model of 
computation is, in practice, has been a focus of some of our research.  
We have designed, implemented and evaluated two different SIMD algorithms.
One is based on Munkres's \cite{mu57} algorithm and was possibly the first
SIMD implementation for the assignment problem.  The other \cite{br88}
takes advantage of recent theoretical work \cite{gpv88} on this
problem for the PRAM model.  Furthermore, as a result of discussions at the 
DIMACS workshop, we chose to implement the Auction algorithm \cite{be91}
on a variety of parallel architectures. We detail our insights into
the behaviour of the algorithm and the idosyncracises of the various
architectures we used.

The paper is organized as follows.  
In Section~\ref{defns}, we state the Assignment problem, describe 
the SIMD model and give details of the 
hardware platforms on which we obtained performance results.  
In Section~\ref{munkres}, we describe the algorithm based on
a parallelization of Munkres's algorithm.
In Section~\ref{scale}, we describe an SIMD algorithm based on 
the more recent theoretical work for the PRAM 
model.  Section~\ref{auction} describes our experiences with the
Auction algorithm on a variety of parallel architectures.