割当問題

【わりあてもんだい (assignment problem)】

$|V^{+}|=|V^{-}|\,$ なる2部グラフ $G=(V^{+},V^{-};A)\,$ および各枝 $a\in A\,$ の重み $w(a)\in {\mathbf {R} }\,$が与えられたときに, 枝の重みの和 $\textstyle \sum _{a\in M}w(a)\,$ を最大にする完全マッチング $M\subseteq A\,$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.