Assignment Problems

Eranda Çela

ABSTRACT

Assignment problems arise in different situations where we have to find an optimal way to assign n objects to m other objects in an injective fashion. Depending on the objective we want to optimize, we obtain different problems ranging from linear assignment problems to quadratic and higher-dimensional assignment problems. Assignment problems are a well-studied topic in combinatorial optimization. These problems find numerous applications in production planning, telecommunication, VLSI design, economics, and so on. We introduce the basic problems classified into three groups: linear assignment problems, three- and higher dimensional assignment problems, and quadratic assignment problems and problems related to it. For each group of problems we mention applications, show basic properties, and describe briefly some of the most successful algorithms used to solve these problems.