Algorithms for assignment problems on an array processor (Q1124328)

The paper presents parallel algorithms designed for assignment problems, in particular the quadratic assignment problem. The complexity of the algorithms is measured in terms of computer operations. The algorithms are implemented on the Distributed Array Processor (a SIMD computer). It consists of \(n^ 2\) processors organized as a 2-dimensional mesh. Each processor can communicate directly with its four neighbours, but is also connected via row and column highways to a set of edge registers. The authors programmed the algorithms in DAP-FORTRAN. The computational results show that as the problem get larger, so do the savings in computation time.