Assignment problem
In its most general form, the problem is as follows: Alternatively, describing the problem using graph theory: If the numbers of agents and tasks are equal, then the problem is called balanced assignment, and the graph-theoretic version is called minimum-cost perfect matching.
The firm prides itself on speedy pickups, so for each taxi the "cost" of picking up a particular customer will depend on the time taken for the taxi to reach the pickup point.
Its solution is whichever combination of taxis and customers results in the least total cost.
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.
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.
The formal definition of the assignment problem (or linear assignment problem) is Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as: The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.
Another naive solution is to greedily assign the pair with the smallest cost first, and remove the vertices; then, among the remaining vertices, assign the pair with the smallest cost; and so on.
Fortunately, there are many algorithms for finding the optimal assignment in 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.
In the balanced assignment problem, both parts of the bipartite graph have the same number of vertices, denoted by n. One of the first polynomial-time algorithms for balanced assignment was the Hungarian algorithm.
This is currently the fastest run-time of a strongly polynomial algorithm for this problem.
weakly-polynomial time in a method called weight scaling.
[4][5][6] In addition to the global methods, there are local methods which are based on finding local updates (rather than full augmenting paths).
These methods have worse asymptotic runtime guarantees, but they often work better in practice.
[1]: 3 A simple technical way to solve this problem is to extend the input graph to a complete bipartite graph, by adding artificial edges with very large weights.
As shown by Mulmuley, Vazirani and Vazirani,[8] the problem of minimum weight perfect matching is converted to finding minors in the adjacency matrix of a graph.
Using the isolation lemma, a minimum weight perfect matching in a graph can be found with probability at least 1⁄2.
There is also a constant s which is at most the cardinality of a maximum matching in the graph.
The main problem with this doubling technique is that there is no speed gain when
The Hungarian algorithm can be generalized to solve the problem in
[1]: 6 The assignment problem can be solved by presenting it as a linear program.
The variable is 1 if the edge is contained in the matching and 0 otherwise, so we set the domain constraints:
While this formulation allows also fractional variable values, in this special case, the LP always has an optimal solution where the variables take integer values.
This is because the constraint matrix of the fractional LP is totally unimodular – it satisfies the four conditions of Hoffman and Gale.
Other approaches for the assignment problem exist and are reviewed by Duan and Pettie[9] (see Table II).
Their work proposes an approximation algorithm for the assignment problem (and the more general maximum weight matching problem), which runs in linear time for any fixed error bound.
In the many-to-many assignment problem,[10] each agent i may take up to ci tasks (ci is called the agent's capacity), and each task j may be taken by up to dj agents simultaneously (dj is called the task's capacity).
), then the problem is balanced, and the goal is to find a perfect matching (assign exactly ci tasks to each agent i and exactly dj agents to each task j) such that the total cost is as small as possible.
Another generalization of the assignment problem is extending the number of sets to be matched from two to many.
This results in Multidimensional assignment problem (MAP).
