Selected topics on assignment problems (Q697571)

This paper deals with a fundamental problem in operations research: the assignment problem; it also covers generalizations of this problem. (The assignment problem deals with the question how to assign \(n\) items (jobs, students) to \(n\) other items (machines, tasks).) After reviewing some basic results, the current status of complexity bounds of algorithms for different versions of the problem is discussed. In particular, algorithms for (special cases of) the linear sum assignment problem, and the linear bottleneck assignment problem are described. Further, multidimensional assignment problems are described. Two special cases, the axial three-dimensional assignment problem, and the planar three-dimensional assignment problem are treated in depth. Further, the quadratic assignment problem (QAP) is extensively discussed. The following topics are described: applications of the QAP, different formulations, how to compute lower bounds (linearization, eigenvalue bounds), and solution methods (like simulated annealing, tabu search). Asymptotic results come into play, and finally the biquadratic assignment problems is treated. The paper closes with a list of 154 references.