Pair people to tasks, students to schools, donors to recipients — as many valid matches as possible, none double-booked. The assignment problem, solved.
Bipartite MatchingLive
assignment problem
Controls
Presets
Maximum bipartite matching pairs items from two groups — workers to jobs, students to schools, organs to recipients — so that as many valid pairings as possible are made, with no one assigned twice. Kuhn's algorithm repeatedly finds augmenting paths that improve the matching. The green edges are the optimal assignment.
∣M∣=covermin∣C∣=0(Ko¨nig: max matching=min vertex cover)
Reading this result: Only 0 of 6 paired: at 40% density the graph is too sparse, so many workers have no eligible job and augmenting paths run out early.
Runs locally in your browser — free forever. Scale to the cloud when reality gets heavy.
★ Sign in to save this setupSave your tuned setup, or drop this simulation into your own site, docs, or course page.
How it works
Maximum bipartite matching finds the largest set of pairings between two groups such that each valid edge respects the constraints and no node is used twice. Kuhn's algorithm repeatedly searches for augmenting paths that grow the matching. It underlies job assignment, kidney-exchange programs, and ad allocation, and is the combinatorial core of many scheduling systems.
The algorithm (augmenting paths)▾
Kuhn's algorithm builds the matching greedily. For each unmatched node on the left, it runs a depth-first search for an augmenting path — a path that alternates between unmatched and matched edges and ends at an unmatched node on the right. Flipping the matched/unmatched status along that path increases the matching size by exactly one. Repeat until no augmenting path exists; by Berge's theorem, the matching is then maximum.
The mathematics▾
Given a bipartite graph G = (U ∪ V, E) with edges only between U and V, a matching M ⊆ E is a set of edges with no shared endpoints. A vertex is 'saturated' if an edge of M touches it. A path is augmenting if it starts and ends at unsaturated vertices and alternates E∖M, M, E∖M, …. Berge's theorem: M is maximum ⇔ G has no M-augmenting path. König's theorem further links the maximum matching to the minimum vertex cover in bipartite graphs.
Complexity▾
Kuhn's algorithm runs in O(V · E): each of the V left vertices triggers one DFS costing O(E). For dense or weighted assignment problems, the Hopcroft–Karp algorithm improves this to O(E · √V), and the Hungarian algorithm solves the weighted minimum-cost version in O(V³).
Assumptions & limits▾
This model assumes an unweighted bipartite graph — every valid pairing counts equally, and the goal is to maximize the number of matches. It does not handle preferences or costs (use the Hungarian algorithm for weighted assignment), capacities greater than one per node (that is a flow problem), or non-bipartite graphs (which need Blossom's algorithm).
Where it's used▾
Job and shift assignment, matching medical residents to hospitals, kidney-exchange and organ-donor programs, allocating ads to slots, scheduling exams to rooms, and pairing tasks to machines. Any 'assign each of these to one of those, without conflicts' problem is bipartite matching in disguise.
✦
Ask the AI about this model
The math, the assumptions, real-world uses, or a code translation — explained for this exact simulation.
Is this bipartite matching assignment tool really free?▾
Yes. Bipartite Matching runs entirely in your browser using your device's own compute, so local use is free forever. You only pay Compute Tokens if you scale a job to the cloud.
Do I need to install anything?▾
No. Everything runs client-side in a modern browser — no downloads, no license, no account required to start.
Can I save or share my simulation?▾
Create a free account to save projects, and use a shareable embed or minted DOI to publish a live, interactive version anywhere.
How accurate are the results?▾
The solver uses established numerical methods, but results are for research and educational purposes and should be validated against experiment or professional review before you rely on them.