割当問題

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

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle |V^+| = |V^-|\,} なる2部グラフ $G=(V^{+},V^{-};A)\,$ および各枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a \in A\,} の重み $w(a)\in {\mathbf {R} }\,$が与えられたときに, 枝の重みの和 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle \sum_{a \in M}w(a)\,} を最大にする完全マッチング $M\subseteq A\,$ を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.