An O(1) approximate parallel algorithm for the n-task-n-person assignment problem
Yong Beom Cho, T. Kurokawa, Yoshiyasu Takefuji, H.S Kim · 2005
A parallel algorithm for the n-task-n-person assignment problem is presented in this paper. The proposed algorithm is based on the artificial neural network model where a large number of simple processing elements are used. Through a large number of simulation runs, it was empirically shown that the state of the system can converge to the solution within a hundred iteration steps regardless of the problem size n. The proposed algorithm using n/sup 2/ processing elements requires computational bounds of a nearly O(1) time.