Content deleted Content added
Infrogmation (talk | contribs) m Reverted to last edit by Anonymoues |
m a defined type of mathematical problem |
||
Line 1:
<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>
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>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>
For example, the a's could be workers and the b's projects. ▼
<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>
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><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>The problem is "linear" because the "cost function" C() depends only on the particular pairing (a, b) and is independent of all other pairings.
Links: [http://forum.swarthmore.edu/epigone/comp.soft-sys.matlab/bringhyclu],[http://www.soci.swt.edu/capps/prob.htm],[http://mat.gsia.cmu.edu/GROUP95/0577.html],[http://www.informs.org/Conf/WA96/TALKS/SB24.3.html].
| |||