linear-assignment-js v1.0.10
Linear Assignment
This repository is a simple and general API to use the Linear Assignment Problem Algorithm.
It uses the LAP-JV implemented from here. These are almost the same, but I've added the capabilities to also account for an unbalanced cost matrix. For a visual example, check out the problem adapted to show t-SNE embeddings in a square grid on observable: t-SNE Grid live.
In the example above, they assign n points to n assignees. For example, if I wanted to assign 10 taxi drivers to 10 people on the map. I could compute the distance of each taxi driver to each person (n by n matrix where rows are taxi drivers and the column is the distance to each person). Then I could use the Linear assignment problem to compute the optimal assignments such that we minimize the total sum of distances to the assignments.
But what if there are only 5 taxi drivers and 20 people who want a taxi? This is an unbalanced problem and would result in a cost matrix of 5 x 20.
This package will take in this non-square matrix and return the 5 best assignments. Whereas you could not do this with the previous javascript implementation above out-of-the-box.
Usage
Install via npm like this:
npm install linear-assignment-js
Then you can use it by importing the default function
import * as linearAssignment from "linear-assignment-js";
// const linearAssignment = require("linear-assignment-js");
Then you can interface with the function like this
const taxiDriverLocations = [
[0, 0],
[1, 1],
];
const peopleCallingTaxiLocations = [
[5, 4],
[1, 0],
[1, 1],
[-1, 1],
];
const assignments = linearAssignment.assign({
points: peopleCallingTaxiLocations,
assignTo: taxiDriverLocations,
});
/*
output interpretation:
assignment = [ 1, 2 ]
taxi driver 0 was assigned to person 1 at location (1,0)
taxi driver 1 was assigned to person 2 at location (1,1)
*/