Assignment problem

related topics
{math, number, function}
{rate, high, increase}
{car, race, vehicle}
{company, market, business}
{service, military, aircraft}

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph.

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

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.

Contents

Algorithms and generalizations

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.

The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost 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. If the cost function involves quadratic inequalities it is called the quadratic assignment problem.

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

Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as:

Full article ▸

related documents
Ring (mathematics)
Idempotence
Richard's paradox
Extended real number line
Presburger arithmetic
Preorder
Splitting lemma
Haar measure
Chain rule
Unicity distance
Meromorphic function
Axiom of pairing
Merkle-Hellman
Boolean ring
ML (programming language)
Legendre symbol
Queue (data structure)
Trie
Functional analysis
Oracle machine
Definable real number
Mathematical model
Monster group
B-tree
Elementary group theory
Generalized mean
XSL Transformations
Examples of groups
Associativity
Base (topology)