Jump to content

Assignment problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Anonymoues (talk | contribs) at 02:24, 27 October 2002 (FOLDOC import). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

An assignment problem (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.

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.

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 permission. Update as needed.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Assignment_problem&oldid=387815"