Assignment problem: Difference between revisions

Revision as of 17:42, 28 June 2003

Revision as of 14:08, 4 August 2003

Line 1:

An '''assignment problem''' is any mathematical problem whose solution consists of assigning members of one set to members of another set if each set is of equal size and each element is assigned to exactly one element from the other set.

<p>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):</p>

<p>OneIt 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):</p>.

<p>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, (obviously) there exists some function C, that maps one of the 'A' elements, to one of the 'B' elements in a one-to-one manner.</p>

<p>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, (obviously) there exists some function C, that maps one of the 'A' elements, to one of the 'B' elements in a one-to-one manner.</p>

<p>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'.</p>

<p>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'.</p>

<p><b>Mathematical Definition</b>: An <b>assignment problem</b> (or "linear assignment") is any problem involving minimising the sum of C(a, b) over a set P of pairs (a, b) where a is an element of some set A and b is an element of set B, and C is some function, under constraints such as "each element of A must appear exactly once in P" or similarly for B, or both.</p>

<p><b>Mathematical Definition</b>: An <b>assignment problem</b> (or "linear assignment") is any problem involving minimising the sum of C(a, b) over a set P of pairs (a, b) where a is an element of some set A and b is an element of set B, and C is some function, under constraints such as "each element of A must appear exactly once in P" or similarly for B, or both.</p>

<p>For example, the a's could be workers and the b's projects.</p>

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

The problem is "linear" because the "cost function" C() depends only on the particular pairing (a, b) and is independent of all other pairings.</p>

== External Links ==