Bipartite Matching and the Assignment Problem

A bipartite graph has two distinct sets of nodes — say, orders on one side and available counterparties on the other — with edges only ever running between the two sets, never within one. Two closely related problems live on this structure. Maximum bipartite matching asks for the largest possible set of pairings such that no node is used twice — useful when you just want to match as many orders to counterparties as capacity allows. The assignment problem goes further: every possible pairing has a cost or value attached (say, expected slippage for routing an order to a given venue), and you want the one-to-one matching that minimizes total cost, not just the biggest matching.

Maximum bipartite matching is solved by repeatedly finding "augmenting paths" — a chain that alternates between unmatched and matched edges, starting and ending at unmatched nodes, which lets you flip the whole chain to add one more match — until no such path exists. The weighted assignment problem is classically solved by the Hungarian algorithm, which runs in polynomial time ($O(n^3)$ for $n$ items per side) by iteratively adjusting a system of dual prices until an all-zero-cost perfect matching is found; modern implementations (e.g. scipy.optimize.linear_sum_assignment) hide this machinery behind a single function call.

A concrete example: matching 5 pending orders to 5 execution venues where a cost matrix gives expected market impact for each order-venue pair, the assignment algorithm returns the one-to-one routing that minimizes total expected impact across all five orders simultaneously — not the routing that looks best order-by-order, which can be a worse combination overall.