Content deleted Content added
COPknowledge (talk | contribs) m Added generalization of the wto-dimensional assignment problem to multiple dimensions (i.e., two or more), which is the MAP |
Tag: Reverted |
||
Line 12:
Now, suppose that there are ''four'' taxis available, but still only three customers. This is an ''unbalanced assignment'' problem. One way to solve it is to invent a fourth dummy task, perhaps called "sitting still doing nothing", with a cost of 0 for the taxi assigned to it. This reduces the problem to a balanced assignment problem, which can then be solved in the usual way and still give the best solution to the problem.
An alternate example: Suppose the military wants to assign its soldiers (the agents) to particular countries (tasks). Each soldier has a ranked list of countries they want to go to (weights on the edges). The problem is to assign soldiers to countries such that as many soldiers as possible get close to their top pick.
Similar adjustments can be done in order to allow more tasks than agents, tasks to which multiple agents must be assigned (for instance, a group of more customers than will fit in one taxi), or maximizing profit rather than minimizing cost.
| |||