Content deleted Content added
Count Count (talk | contribs) Reverted 1 edit by 39.34.155.247 (talk): Spam |
|||
Line 39:
The greedy algorithm would assign Task 1 to Alice and Task 2 to George, for a total cost of 9; but the reverse assignment has a total cost of 7.
Fortunately, there are many algorithms for finding the optimal assignment in time [[polynomial time|polynomial]] in ''n''. The assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], or in worst-case polynomial time using the [[ellipsoid method]], each specialization has a smaller solution space and thus more efficient algorithms designed to take advantage of its special structure.
=== Balanced assignment ===
| |||