Massively parallel augmenting path algorithms for the assignment problem |
| |
Authors: | S Storøy T Sørevik |
| |
Affiliation: | 1. Department of Informatics, University of Bergen, Thorm?hlensg. 55, 5020, Bergen, Norway
|
| |
Abstract: | In this paper we describe how to apply fine grain parallelism to augmenting path algorithms for the dense linear assignment
problem. We prove by doing that the technique we suggest, can be efficiently implemented on commercial available, massively
parallel computers. Using n processors, our method reduces the computational complexity from the sequentialO(n
3) to the parallel complexity ofO(n
2). Exhaustive experiments are performed on a Maspar MP-2 in order to determine which of the algorithmic flavors that fits
best onto this kind of architecture. |
| |
Keywords: | 90C08 65E10 |
本文献已被 SpringerLink 等数据库收录! |
|