割当問題
2007年7月9日 (月) 15:03時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【わりあてもんだい (assignment problem)】''' $|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与...')
【わりあてもんだい (assignment problem)】
$|V^+| = |V^-|$ なる2部グラフ $G = (V^+, V^-; A)$ および各枝 $a \in A$ の重み $w(a) \in {\bf R}$が与えられたときに, 枝の重みの和 $\sum_{a \in M}w(a)$ を最大にする完全マッチング $M \subseteq A$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.