ABSTRACT
In the simple assignment problem, 1 we seek to pair up elements from two disjoint sets of equal size. We might call these sets A and J to suggest agents (who will do work) and jobs (work for agents to do). Essential for the simple assignment problem is that the number of jobs equals the number of agents (|A| = |J| = n), each agent can do each job, but at a cost; jobs must be done by exactly one agent; and agents can only do exactly one job. We seek to assign all of the jobs to agents (or equivalently, all of the agents to jobs) in such a way as to minimize cost.
