Assignment problem: Difference between revisions

Revision as of 06:04, 15 May 2003

Revision as of 06:06, 15 May 2003

Line 1:

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.

HOW ABOUT A REDIRECT TO LINEAR PROGRAMMING?

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.

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

----

''This article was originally based on material from [[FOLDOC]], used with [[Public Domain Resources/Foldoc license|permission]]. Update as needed.''