Formal Mathematical Definition
The formal definition of the assignment problem (or linear assignment problem) is
- Given two sets, A and T, of equal size, together with a weight function C : A × T → R. Find a bijection f : A → T such that the cost function:
-
- is minimized.
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.
The problem can be expressed as a standard linear program with the objective function
subject to the constraints
The variable represents the assignment of agent to task, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is totally unimodular. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.
Read more about this topic: Assignment Problem
Famous quotes containing the words formal, mathematical and/or definition:
“I will not let him stir
Till I have used the approvèd means I have,
With wholesome syrups, drugs, and holy prayers,
To make of him a formal man again.”
—William Shakespeare (1564–1616)
“An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.”
—Susan Faludi (20th century)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)