Munkres

Optimally pair up two sets (workers to jobs, drivers to riders, bids to items) to minimize total cost.

Given a cost matrix where matrix[y][x] is the cost of pairing item y with item x, munkres returns the one-to-one assignment with the lowest possible total cost. It’s a fast, dependency-free implementation of the Munkres (Hungarian) algorithm.

Reach for it whenever you have a table of pairing costs (or profits) and need the optimal matching rather than a greedy guess.

Features

• Flexible: number or bigint costs; square (NxN) or rectangular (MxN) matrices; any MatrixLike input (arrays, typed arrays, custom indexables).
• Fast: O(M²N) time when M ≤ N (O(MN²) otherwise) and only O(M + N) extra memory. Benchmarks below.
• Typed & dependency-free: first-class TypeScript types, zero runtime dependencies, ships both ESM and CommonJS.
• Robust: force an assignment with -Infinity or avoid one with Infinity; built-in helpers for building and transforming matrices.

Install

npm install munkres

yarn add munkres

pnpm add munkres

jsr add @munkres/munkres

Usage

import { munkres } from "munkres";

// matrix[y][x] = cost of assigning worker y to job x
const costMatrix = [
  [1, 2, 3],
  [2, 4, 6],
  [3, 6, 9],
];

const assignments = munkres(costMatrix);
// → [[0, 2], [1, 1], [2, 0]]   (worker 0 → job 2, worker 1 → job 1, worker 2 → job 0)

Each result is a [y, x] pair (row, then column). The result has min(rows, cols) pairs; if there are more workers than jobs (or vice versa), the unmatched ones are simply absent.

Maximizing instead of minimizing? Convert your profit matrix to a cost matrix first:

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

const profitMatrix = [
  [9, 8, 7],
  [8, 6, 4],
  [7, 4, 1],
];

const costMatrix = copyMatrix(profitMatrix);
invertMatrix(costMatrix); // flip profits into costs
const assignments = munkres(costMatrix);
// → [[0, 2], [1, 1], [2, 0]]

API

munkres(costMatrix, options?)

Runs the algorithm and returns a set of optimal [y, x] assignment pairs. If several optimal assignments exist, one is returned.

• costMatrix: a MatrixLike<number> or MatrixLike<bigint> where costMatrix[y][x] is the cost of assigning worker y to job x. Costs are minimized, so use -Infinity to force an assignment (chosen whenever possible) and Infinity to avoid one (used only as a last resort, when no finite alternative exists).
• options.finite (boolean, default false): promise the matrix is all-finite and in-range, skipping input validation for a small speedup on large matrices. If the promise is broken, the result is undefined (it won’t throw). See MunkresOptions.

Returns Pair<number>[], an array of [y, x] pairs, length min(rows, cols).

Throws

• TypeError: a number matrix contains NaN. (Use Infinity to avoid an assignment instead.)
• RangeError: a number matrix’s value range (max - min) exceeds Number.MAX_VALUE / 2 and could overflow. Scale the matrix down, or use bigint.

Precision: the number path uses 64-bit floats. For integer costs that need an exact optimum (especially near or beyond Number.MAX_SAFE_INTEGER), use a bigint matrix for arbitrary precision.

Types

• Matrix<T>: a 2D matrix, T[][].
• MatrixLike<T>: a read-only 2D matrix accepting any ArrayLike (arrays, typed arrays, custom indexables).
• Pair<A, B = A>: a [A, B] tuple.
• MunkresOptions: the options object for munkres().

Helpers

Utilities for building and transforming cost matrices:

Benchmarks

Performance is tracked automatically on every release and every commit to main:

• Release-over-release trend →: how performance changes across published versions.
• Per-commit history →: fine-grained regression tracking.
• Run it in your browser →: try it on your own inputs.
• Run locally →: See the contributing guide.

As a ballpark (Apple M2, v2.1.1):

Contributing

Contributions are welcome. See the contributing guide for local setup, tests, and the style guide.

• Questions / discussion: GitHub Discussions
• Bugs: Issue tracker
• Feature requests: open an issue describing the feature and its benefit.

License

MIT © Michael Rojas