Assignment problem: Difference between revisions

Revision as of 14:08, 4 August 2003

Revision as of 20:05, 13 August 2003

Line 1:

An '''assignment problem''' is any mathematical optimization problem whose solution consists of assigning members of one set, say assignees, to members of another set, ifsay tasks. Provided each set is of equal size and each element is assigned to exactly one element from the other set. Associated with each possible pairing (assignee, task) is a cost. The optimal assignment will optimize the sum of the assignment costs.

The assignment problem is a special case of another optimization problem known as the '''transportation problem''', witch in turn is a special case of a problem known as '''maximal flow problem''', which in turn is a special case of a '''linear program'''. While it is possible to solve all these problems with the '''simplex algorithm''', each of these problems has more efficient algorithms designed to take advantage of their special structure. It is know that an algorithm exists to solve the assignment problem within time bounded by a polynomial expression of the number of assignees.

It is one of a class of general scientific problems, that has a known approximate solution (one that can be calculated in a reasonable amount of time).

A problem may be classified as an 'assignment problem' if the nature of the problem is such that there exist 2 sets of data, each with identical numbers of elements. Then there exists some function C, that mapsprovides the cost of assigning one of the 'A' elements, to one of the 'B' elements in a one-to-one manner.

As opposed to, for instance, a function D, which maps several elements of 'A' to a single element of 'B', or vice-versa; in which case one cannot say that this is an 'assignment problem'.

Line 11:

For example, the a's could be workers and the b's projects.

The problem is "linear" because the "cost function" C()to dependsbe onlyoptimized onas thewell particularas pairingall (a,the b)constraints andcan isbe independentexpressed of allas otherlinear pairingsequations.

== External Links ==