\relax 
\bibstyle{alpha}
\citation{mu57}
\citation{br88}
\citation{gpv88}
\citation{be91}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {1}Introduction}{1}}
\newlabel{intro}{{1}{1}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {2}Definitions and Models}{1}}
\newlabel{defns}{{2}{1}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {2.1}The Assignment Problem}{1}}
\newlabel{assign_prob}{{2.1}{1}}
\citation{ho86}
\citation{rjn90}
\citation{re78}
\citation{ja90}
\citation{bl90}
\citation{nic90}
\citation{ch90}
\citation{hora88}
\citation{gpv88}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {2.2}The SIMD Computing Model}{2}}
\newlabel{model}{{2.2}{2}}
\citation{ho87,ra87}
\citation{ho87}
\citation{re78}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {3}Munkres's Algorithm}{3}}
\newlabel{munkres}{{3}{3}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {3.1}The Munkres Modification of the ``Hungarian'' Solution}{3}}
\newlabel{munkres_modify}{{3.1}{3}}
\citation{br88}
\citation{gpv88}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {3.2}Performance of the Parallel Munkres-style Algorithm}{4}}
\newlabel{munkres_results}{{3.2}{4}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {1}{\ignorespaces Performance of Munkres's algorithm on AP2S}}{5}}
\newlabel{fig_1_munkres_results}{{1}{5}}
\citation{be86}
\citation{va80}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {4}Parallel Cost-scaling Algorithm}{6}}
\newlabel{scale}{{4}{6}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.1}Description of the Algorithm}{6}}
\newlabel{desc_cost_scale}{{4.1}{6}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {1}{\ignorespaces Procedure Match()}}{7}}
\newlabel{match_procedure}{{1}{7}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {2}{\ignorespaces Procedure Push\unhbox \voidb@x \kern .06em \vbox {\hrule width.3em}Relabel\unhbox \voidb@x \kern .06em \vbox {\hrule width.3em}Matching( )}}{7}}
\newlabel{push_relabel_matching}{{2}{7}}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {3}{\ignorespaces Procedure Shortest\unhbox \voidb@x \kern .06em \vbox {\hrule width.3em}Path\unhbox \voidb@x \kern .06em \vbox {\hrule width.3em}Matching( )}}{8}}
\newlabel{shortest_path_matching}{{3}{8}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {2}{\ignorespaces Push Relabel Matching Algorithm ($w(i, j) = i \times j$)}}{8}}
\newlabel{fig_results_scale}{{2}{8}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {4.2}Performance Results of the Parallel Cost-Scaling Algorithm}{8}}
\newlabel{results_scale}{{4.2}{8}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {3}{\ignorespaces Shortest Path Matching Algorithm ($w(i, j) = i \times j$)}}{9}}
\newlabel{fig_distance_scale}{{3}{9}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {4}{\ignorespaces Combination of Shortest Path and Push Relabel Matching Algorithm ($w(i, j) = i \times j$)}}{9}}
\newlabel{fig_combine_scale}{{4}{9}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {5}{\ignorespaces Average Performance of the Push Relabel and Shortest Path passes, and of the entire algorithm for large input size (random 11-bit data)}}{9}}
\newlabel{fig_xxx_scale}{{5}{9}}
\citation{be91}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {5}The Auction algorithm}{10}}
\newlabel{auction}{{5}{10}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.1}Description of the Auction algorithm}{10}}
\newlabel{auction_desc}{{5.1}{10}}
\citation{bct91}
\citation{ca91}
\citation{weze91,beca89}
\citation{weze91,beca89}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {6}{\ignorespaces Fraction of bids with a given number of unassigned persons}}{11}}
\newlabel{many_bids_for_few}{{6}{11}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Combined Forward-Reverse Auction.}{11}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Gauss-Seidel vs. Jacobi.}{11}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.2}Characteristics of the Auction algorithm}{12}}
\newlabel{auction_charac}{{5.2}{12}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.3}SIMD Implementation}{12}}
\newlabel{simd}{{5.3}{12}}
\citation{rjn90}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {7}{\ignorespaces Results on SIMD Machines}}{13}}
\newlabel{auction_simd_results}{{7}{13}}
\@writefile{toc}{\string\contentsline\space {paragraph}{Results and Discussion}{13}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {8}{\ignorespaces Time to perform specified operation on the Wavetracer (in $\mu $sec)}}{14}}
\newlabel{wave_perform}{{8}{14}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {9}{\ignorespaces Time to perform specified operation on the MasPar (in $\mu $sec)}}{14}}
\newlabel{simd_myth_bit_serial}{{9}{14}}
\citation{weze91}
\citation{weze91}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {4}{\ignorespaces Effect of breaking pipeline in SIMD machines}}{15}}
\newlabel{pipeline}{{4}{15}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {10}{\ignorespaces Time to transfer data from a binaty file on the DEC workstation- host into the memory of MasPar array processors.}}{16}}
\newlabel{simd_read_data}{{10}{16}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.4}Shared Memory Implementation}{16}}
\newlabel{shmem}{{5.4}{16}}
\citation{la77}
\citation{su192}
\citation{beca89}
\@writefile{toc}{\string\contentsline\space {paragraph}{Results and Discussion.}{17}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {11}{\ignorespaces Performance results on shared memory system}}{17}}
\newlabel{fig_shmem_results}{{11}{17}}
\@writefile{toc}{\string\contentsline\space {paragraph}{A Note on Asynchronous Implementations}{17}}
\citation{sun91}
\@writefile{lof}{\string\contentsline\space {figure}{\string\numberline\space {5}{\ignorespaces Variation of average bid time for large problem sizes}}{18}}
\newlabel{fluctuate}{{5}{18}}
\@writefile{toc}{\string\contentsline\space {subsection}{\string\numberline\space {5.5}Distributed Implementation}{18}}
\newlabel{dist}{{5.5}{18}}
\citation{po80}
\citation{sun92}
\@writefile{toc}{\string\contentsline\space {paragraph}{Results and Discussion}{19}}
\@writefile{lot}{\string\contentsline\space {table}{\string\numberline\space {12}{\ignorespaces Time (in msec) to accumulate partial results.}}{20}}
\newlabel{dist_gather_results}{{12}{20}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {6}Conclusions}{20}}
\newlabel{end}{{6}{20}}
\@writefile{toc}{\string\contentsline\space {section}{\string\numberline\space {7}Acknowledgements}{21}}
\newlabel{ack}{{7}{21}}
\bibdata{../ref,dim_ref}