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 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.

Another kinds are the quadratic assignment problem, bottleneck assignment problem.

The assignment problem is a special case of another optimization problem known as the transportation problem, which is a special case 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 problem has more efficient algorithms designed to take advantage of its special structure. Algorithm are known that solve the linear assignment problem within time bounded by a polynomial expression of the number of agents.

The restrictions on agents, tasks and cost in the (linear) assignemnt problem could be relaxed, as shown in the example below.

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 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 cost function C:A×T→R. Find the bijection f:A→T such that:

is minimized.