Assignment problem: Difference between revisions

Revision as of 02:54, 21 March 2005

Revision as of 20:09, 22 March 2005

Line 25:

The formal definition of the '''assignment problem''' (or '''linear assignment problem''') is

:Given two sets, ''A'' and ''T'', of equal size, together with a cost[[weight function]] ''C'' : ''A'' × ''T'' → '''[[real number|R]]'''. Find the [[bijection]] ''f'' : ''A'' → ''T'' such that the [[cost function]]:

::<math>\sum_{a\in A}C(a,f(a))</math>

:is minimized.

Usually the weight function is viewed as a square real-valued [[matrix]] ''C'', so that the cost function is written down as:

:<math>\sum_{a\in A}C_{a,f(a)}</math>

The problem is "linear" because the cost function to be optimized as well as all the constraints can be expressed as linear equations.

[[Category:Optimization]]