# assignment problem

The assignment problem is a kind of optimization problem in which the goal is to reduce the total cost of a number of tasks by choosing a particular assignment of those tasks to a number of agents, or task executors. One example might be an algorithm for assigning pieces of work to individual processors of different capacities in a multiprocessor computer. A more real-world example might be Amazon deciding, given a finite number of airplanes, which distribution center should be used, with its fleet, to service a particular set of delivery requests in order to minimize the usage of fuel.

Mathematically, the assignment problem starts with a finite set of agents, $A$, and a finite set of tasks, $T$, where $|A|=|T|$. The cost of a particular agent executing a particular task is a cost, or , function^{} $C:A\times T\to \mathbb{R}$. The goal is to find the bijective mapping $f:A\to T$ assigning agents to tasks such that the cost function

$$\sum _{a\in A}C(a,f(a))$$ |

is minimized.

The cost function can also be viewed as a square real-valued matrix $C$, where ${C}_{i,j}$ is the cost of having agent $i$ execute task $t$, so that the objective function can be written as

$$\sum _{a\in A}{C}_{a,f(a)}$$ |

The problem is “linear” because the cost function to be optimized as well as all the constraints contain only linear terms.

This entry was adapted from the Wikipedia article http://en.wikipedia.org/wiki/Assignment_problemAssignment problem as of January 13, 2007.

Title | assignment problem |
---|---|

Canonical name | AssignmentProblem |

Date of creation | 2013-03-22 16:33:40 |

Last modified on | 2013-03-22 16:33:40 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 8 |

Author | PrimeFan (13766) |

Entry type | Definition |

Classification | msc 90C27 |

Synonym | linear assignment problem |