LAP-JV

Linear Assignment Problem — algorithm by R. Jonker and A. Volgenant

“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.

Usage

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);
  // 4

Here 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.