割当問題

出典: ORWiki

【わりあてもんだい (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\,$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用フロー問題（最小費用流問題）の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.