Munkres

A lightweight and efficient implementation of the Munkres (Hungarian) algorithm for optimal assignment.

Features

1. Flexible

   • Use number or bigint matrices.
   • Use square (NxN) or rectangular (MxN) matrices.
   • Works with any MatrixLike input. Use arrays, typed arrays, custom objects, etc.

2. Fast (benchmarks)

   • O(M²N) when M <= N

   • O(MN²) when M > N

3. Efficient

   • O(M + N) memory

4. Robust

   • Supports -Infinity and Infinity values.
   • Helper methods provided for creating and modifying matrices.

Getting Started

Install

NPM:

npm install munkres

Yarn:

yarn add munkres

JSR:

jsr add @munkres/munkres

Usage

With a cost matrix:

import munkres from "munkres";

// Create a cost matrix. Cell [y, x] is the cost
// of assigning the y-th worker to the x-th job.
const costMatrix = [
  [1, 2, 3],
  [2, 4, 6],
  [3, 6, 9],
];

// Find a set of optimal assignments pairs (y, x).
const assignments = munkres(costMatrix);

console.log(assignments);
// Output: [[0, 2], [1, 1], [2, 0]]

With a profit matrix:

import { munkres, copyMatrix, invertMatrix } from "munkres";

// Create a profit matrix. Cell [y, x] is the
// profit of assigning the y-th worker to the x-th job.
const profitMatrix = [
  [9, 8, 7],
  [8, 6, 4],
  [7, 4, 1],
];

// Covert the profit matrix into a cost matrix.
const costMatrix = copyMatrix(profitMatrix);
invertMatrix(costMatrix);

// Find a set of optimal assignments pairs (y, x).
const assignments = munkres(costMatrix);

console.log(assignments);
// Output: [[0, 2], [1, 1], [2, 0]]

Skipping input validation on large guaranteed-finite matrices:

import { munkres } from "munkres";

// When you know the matrix contains no Infinity or NaN, `{ finite: true }`
// skips the O(Y*X) validation scan and dispatches straight to the
// all-finite arithmetic path. Faster for large matrices.
const assignments = munkres(largeFiniteCostMatrix, { finite: true });

API

• munkres(costMatrix, options?)

  Executes the Munkres algorithm on the given cost matrix and returns a set of optimal assignment pairs. Even if there are multiple optimal assignment sets, only one is returned.

  Parameters

  • costMatrix: a MatrixLike<number> or MatrixLike<bigint> where costMatrix[y][x] is the cost of assigning worker y to job x. Use Infinity / -Infinity to mark forbidden assignments. The matrix is treated as costMatrix.length × costMatrix[0].length; cells beyond row 0’s width are ignored.
  • options (optional):
    • finite: boolean — when true, promises that the matrix contains no NaN or Infinity and that its range is in-bounds (max(c) - min(c) <= Number.MAX_VALUE / 2). Skips both the finiteness scan and the range check, dispatching straight to the fast all-finite path. If either promise is violated, the result is undefined (may produce a wrong assignment or Infinity / NaN cells; never throws RangeError / TypeError from this path).

  Returns

  An array of [y, x] pairs. The result length is min(rows, cols) and pairs are always [y, x] (row, column) regardless of shape. When rows > cols, the unmatched rows are simply absent from the result; when cols > rows, the unmatched columns are absent.

  Throws

  • TypeError: if a number cost matrix contains NaN. The error message includes the coordinates of the first NaN encountered. Use Infinity for forbidden assignments instead. Skipped under { finite: true }.
  • RangeError: if a number cost matrix has max(c) - min(c) > Number.MAX_VALUE / 2. The algorithm’s worst-case intermediate arithmetic magnitude is 2 * (max - min); this guard keeps all intermediates representable in IEEE-754 double precision. Scale your matrix down, or use a bigint matrix. Skipped under { finite: true }. bigint matrices are exempt entirely.

  Numeric precision

  The number path uses IEEE 754 double-precision arithmetic. For matrices of integer costs where exact optima are required (especially when values approach or exceed Number.MAX_SAFE_INTEGER), pass a bigint cost matrix to use the arbitrary-precision path. Floating-point inputs are inherently approximate; the number path may return a valid but suboptimal assignment when precision is lost in slack comparisons.

Types

• Matrix<T>: A generic 2D matrix (i.e. T[][]).

• MatrixLike<T>: A generic read-only 2D matrix.

  • Can be made from any ArrayLike objects (i.e. any indexable object with a numeric length property). This allows for more flexibility, such as matrices made with typed arrays or objects.

• Pair<A, B = A>: A generic pair (i.e. [A, B]).

Helpers

1. copyMatrix(matrix): Creates a copy of the given matrix.

2. createMatrix(workers, jobs, callbackFn): Generates a matrix based on the given workers, jobs, and callback function.

3. genMatrix(numRows, numCols, callbackFn): Generates a matrix based on the given dimensions and a callback function.

4. getMatrixMax(matrix): Finds the maximum value in a given matrix.

5. getMatrixMin(matrix): Finds the minimum value in a given matrix.

6. invertMatrix(matrix, bigVal?): Inverts the values in the given matrix. Useful for converting between minimizing and maximizing problems. If bigVal is not given, the matrix’s max value is used instead.

7. negateMatrix(matrix): Negates all values in the given matrix. Useful for converting between minimizing and maximizing problems.

Community and Support

Contributions are welcome!

• Questions / Dicussions: Please contact us via GitHub discussions.

• Bug Reports: Please use the GitHub issue tracker to report any bugs. Include a detailed description and any relevant code snippets or logs.

• Feature Requests: Please submit feature requests as issues, clearly describing the feature and its potential benefits.

• Pull Requests: Please ensure your code adheres to the existing style of the project and include any necessary tests and documentation.

For more information, check out the contributor’s guide.

Build

1. Clone the project from github

git clone git@github.com:havelessbemore/munkres.git
cd munkres

1. Install dependencies (this project uses pnpm)

pnpm install

1. Build the project

pnpm run build

This will output ECMAScript (.mjs) and CommonJS (.js) modules in the dist/ directory.

Format

To run the code linter:

pnpm run lint

To automatically fix linting issues, run:

pnpm run format

Test

To run tests:

pnpm test

To run tests with a coverage report:

pnpm run test:coverage

A coverage report is generated at ./coverage/index.html.

Benchmarks

Run benchmarks in your browser.

To run locally:

pnpm run bench

CI / CD

Benchmarks are integrated into our CI/CD pipeline and automatically run with each commit to the main branch. This helps monitor the performance impacts of development, preventing regressions and verifying changes maintain performance standards.

View historical results.

Specs:

• Package version: latest
• Runtime: NodeJS v24
• Benchmarking Tool: tinybench v6
• OS: ubuntu-latest

What the dashboard measures

Each datapoint is per-iteration wall time, averaged across 50 iterations after a warmup pass. Per-iteration cost is dominated by the bench harness itself for large inputs:

• The benchmark generates a fresh cost matrix on every iteration (beforeEach), runs munkres() (the timed window), then clears it (afterEach). Tinybench measures only the munkres() call, but the allocator/GC state at the start of each iteration is shaped by what happened across the surrounding 50 iterations.
• For bigint[2048][2048], the input matrix alone is ~96 MB of boxed BigInts. The algorithm itself completes in ~800 ms (measurable via a one-shot timed call). The dashboard reports ~3 s under the same conditions — the additional ~2 s is per-iteration allocator/GC overhead that compounds across the run.
• For number[4096][4096], the matrix is ~32 MB of doubles (smaller, denser, often SMI-optimized by V8), so the harness overhead is a smaller share.

To stabilize the per-iteration signal, the bench scripts force a synchronous GC between iterations (via globalThis.gc(), enabled by --expose-gc). This pins each iteration to a comparable heap state and reduces run-to-run variance on shared CI runners. The forced GC happens inside afterEach, after the timing window has already closed, so it does not bias the measurement.

Use the dashboard for relative regression detection across commits, not as a measure of algorithm speed in isolation.

Results

Below are the latest results from running locally.

Specs:

• Package version: v2.1.0
• Runtime: NodeJS v24.16.0
• Benchmarking Tool: tinybench v6
• Machine:
  • Model: MacBook Air
  • Chip: Apple M2
  • Memory: 8 GB
  • OS: MacOS Sonoma

number[][]

bigint[][]

Made with ❤️ by Michael Rojas