“A shortest augmenting path algorithm for dense and sparse linear assignment problems,” by R. Jonker and A. Volgenant, Computing (1987) 38: 325. doi:10.1007/BF02278710
Ported to javascript by Philippe Rivière, from the C++ implementation found at https://github.com/yongyanghz/LAPJV-algorithm-c
Added an epsilon to avoid infinite loops caused by rounding errors.
In the Linear Assignment Problem, you have n agents and n tasks, and need to assign one task to each agent, at minimal cost.
First, compute the cost matrix: how expensive it is to assign agent i (rows) to task j (columns).
The LAP-JV algorithm will give an optimal solution:
n = 3, costs = [[1,2,3], [4,2,1], [2,2,2]];
// ^ _ _ _ _ ^ _ ^ _
solution = lap(n, costs);
console.log(solution.col);
// [0, 2, 1]
console.log(solution.cost);
// 4Here agent 0 is assigned to task 0, agent 1 to task 2, agent 2 to task 1, resulting in a total cost of 1 + 1 + 2 = 4.
Cost callback
For performance and usability reasons, the lap function now accepts a cost callback cost(i,j) instead of a cost matrix:
var pos = new Float32Array(1000).map(d => Math.random() * 1000);
lap(pos.length, (i,j) => (pos[i] - j) * (pos[i] - j));The algorithm runs in O(n^2). You can run it directly or as a javascript worker, as in the following example:
In the example above, we assign n points to a grid of n positions. costs[i][j] is the square distance between point i's original coordinates and position j's coordinates. The algorithm minimizes the total cost, i.e. the sum of square displacements.
Comments and patches at Fil/lap-jv.