The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. December 2005 : January - February - March - April - May - June - July - August - September - October - November - December- → 31 December 2005 (Saturday) 25-year-old Scottish human rights worker Kate Burton and her parents are freed unharmed in the Gaza Strip by the Palestinian gunmen who kidnapped them two days earlier. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that... Operations research, operational research, or simply OR, is the use of mathematical models, statistics and algorithms to aid in decision-making. ... Euclid, detail from The School of Athens by Raphael. ...

In its most general form, the problem is as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the total cost of the assignment is minimized.

If the numbers of agents and tasks are equal and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the Linear assignment problem. Commonly, when speaking of the Assignment problem without any additional qualification, then the Linear assignment problem is meant.

The Hungarian algorithm is one of many algorithms that have been devised that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents. In graph theory, Munkres assignment algorithm or the Hungarian algorithm is an algorithm which solves the assignment problem in polynomial time. ...

The assignment problem is a special case of the transportation problem, which is a special case of the maximal flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure. The max flow min cut theorem is a statement in optimization theory about optimal flows in networks. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. ...

Other kinds are the quadratic assignment problem, bottleneck assignment problem. The quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems. ...

Example

Suppose that a taxi firm has three taxis (the agents) available, and three customers (the tasks) wishing to be picked up as soon as possible. The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point. The solution to the assignment problem will be whichever combination of taxis and customers results in the least total cost.

However, the assignment problem can be made rather more flexible than it first appears. In the above example, suppose that there are four taxis available, but still only three customers. Then a fourth dummy task can be invented, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. The assignment problem can then be solved in the usual way and still give the best solution to the problem.

Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.

Formal mathematical definition

The formal definition of the assignment problem (or linear assignment problem) is

Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:

is minimized.

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as: A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ... A bijective function. ... Optimization is a branch of mathematics which is concerned with finding maxima and minima of real-valued functions. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, of elements of a ring-like algebraic structure. ...

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

Marriage Problem

The Marriage Problem is an extension of the assignment problem to the field of Game Theory. For pedagogical purposes the sets A and T are now regarded as the sets of Men (M) and Women (W). The weight function Game theory is a branch of applied mathematics that studies strategic situations where players choose different actions in an attempt to maximize their returns. ... A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ...

C(m,w) = C_m(m,w) + C_w(m,w)

is split into two weight functions C_m and C_w, that represent a measure of how acceptable is each member of the opposite gender to each player respectively (the lower the value of C_m(m,w), the more man m likes woman w). A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more of a weight than others. ...

The bijection between M and W is regarded now as a given configuration of couples. One can pose the same question as in the assignment problem: which configuration will have the lower total cost?. In this context this is equivalent to ask for the distributions of couples that makes Society the happier. However, the social optimum, although the best for society, might not, and probably will not be the best of choices for everyone. It is very likely that even in this state there will be two persons, a man and a woman, which are not married together in the sake of social happiness, but they found each other more attractive than they current spouses. This would leed to the break up of their respective couples and a new couple configuration would raise, with a lower total happiness. Human relationships within an ethnically diverse society For other uses, see Society (disambiguation). ...

In a world of selfish players, as it is usually the case, the social optimum can not be sustained in time due to players are seeking their own satisfaction, and not social goals. One might ask if there is any configuration of couples at all, in which the instability described before don't exists. Such a configuration would be a Nash Equilibrium of this game theoretic problem. In game theory, the Nash equilibrium (named after John Nash, who proposed it) is a kind of optimal collective strategy in a game involving two or more players, where no player has anything to gain by changing only his or her own strategy. ...

The Marriage Problem consist of finding all configurations of couples that are stable against the egoist behavior of players, i.e. that are a Nash Equilibrium. Fortunately, there is always such a state, and usually there are many. Unfortunately the social optimum is rarely a Nash Equilibrium. In game theory, the Nash equilibrium (named after John Nash, who proposed it) is a kind of optimal collective strategy in a game involving two or more players, where no player has anything to gain by changing only his or her own strategy. ... In game theory, the Nash equilibrium (named after John Nash, who proposed it) is a kind of optimal collective strategy in a game involving two or more players, where no player has anything to gain by changing only his or her own strategy. ...

Reference

• For a detailed study of state-of-the-art research in this topic see arxiv.org search engine.