匈牙利算法

顶点势先给每对工人、任务设定一个价格下界。紧边表示目前的下界已经触及真实成本，算法先尝试只用这些边完成分配。冲突出现时，并不立即放弃早先的匹配，而是沿交替路径搬动已有安排。

势调整解决的是“现有紧边不够用”：只抬高交替树中受阻工人的势，同时降低树内任务的势，使已有匹配继续紧，而通向新任务的某条边刚好变紧。匹配大小在增广时增长，对偶目标在正的势调整时增长；二者并非每一步都同步改变。

考虑工人 $A,B,C$ 与任务 $1,2,3$ 的成本：

初始势为 $u=(1,1,1),v=(0,0,0)$，紧边只有 $A1,B1,C3$。先匹配 $A1$，再给 $B$ 找任务时会沿 $B\to 1\to A$ 受阻，此时 $S=\{A,B\},T=\{1\}$。到外部任务的最小松弛量来自 $A2$，为 $\mathrm{\Delta }=1$。

调整后 $u=(2,2,1),v=(-1,0,0)$。边 $A1,B1$ 仍紧，$A2$ 新变紧，于是沿 $B\to 1\to A\to 2$ 增广，将 $A1$ 换成 $B1,A2$，再匹配 $C3$。总代价为 $1+2+1=4$，恰等于势和 $2+2+1-1=4$。这个证书同时说明，若先固定 $A1$ 再让 $B$ 选剩余最便宜任务，会花费 $1+4+1=6$，逐行贪心并不正确。

矩形问题可以补虚拟行列，但虚拟成本必须表达真实的未指派代价。禁止配对的边应被排除；若受阻时没有任何有限的跨出候选，就应报告不存在完美匹配，而不能继续使用无穷大的势更新。求最大权时可把所有成本变号，再使用同一套最小化公式。

稠密实现为每个外部任务维护来自 $S$ 的最小松弛量；每加入一个工人，只需扫描一行来更新它。一次增广至多扩展 $n$ 个任务，耗时 $O(n^2)$，共 $n$ 次，得到 $O(n^3)$ 算术操作界。若每次都重新搜索全部匹配或重算全部松弛量，不能自动得到这个界；大整数运算的位成本也需另外计算。

任务调度、数据关联和多目标跟踪可用成本矩阵表达两侧一对一的选择。一般图的带权匹配不满足二分结构，不能直接套用本算法。拟阵交算法理路拟阵交算法Matroid intersection algorithm · Unweighted matroid intersection在两个有限拟阵的交换有向图中寻找最短增广路，以独立性 oracle 构造最大公共独立集并在无路时输出秩和证书。能把二分匹配编码为两个分割拟阵的交，但它使用交换图和独立性查询；这种更一般的表达并不直接继承这里的势更新和稠密时间界。

二分匹配多胞形理路二分图匹配多胞形Bipartite matching polytope证明二分图的非负边变量与顶点度上界已给出匹配凸包，并用交替扰动区分分数可行点和分数顶点。解释了为什么非负边变量与度约束已足以给出整数顶点。若输入是一份长期分数计划而不是单次成本矩阵，Birkhoff–von Neumann 分解理路双随机矩阵的 Birkhoff–von Neumann 分解Birkhoff–von Neumann theorem · Doubly stochastic matrix decomposition在正支撑图中反复寻找完美匹配并扣除最小边权，把任意双随机矩阵精确拆成置换矩阵的凸组合。逐次扣除带权完美匹配，把双随机计划还原成可执行排班。