トップ > 数理計画用語集 > 最大カット問題

数理計画用語集

最大カット問題

読み:さいだいかっともんだい
英名:Max Cut Problem
関連半正定値計画問題

最大カット問題とは,重み付きグラフのノードを2つのグループに分割する問題で,グループ分けをした際にカットされるエッジの重み総和を最大化する.ここで,2つのノードが異なるグループに属したとき,その2点をつなぐエッジがカットされたと言う.

ノードの集合としてequationを与え(ノード数は n ),変数としてequationを与える.最大カット問題は次のように定式化される.

equation

なおequationはノード equation 間の重みを表す.上記定式化に対し, 変数equationequationで置き換える変数equationを導入すると,次の問題と同値になる.

equation

ここで制約式 equation を緩和した問題が次の半正定値緩和問題となる.

equation

上記問題に対して,以下の手順により最大カット問題の実行可能解を生成することができる.

(1) equationを満たすequationを求める.

(2) n 次元単位球面上の一様分布に従う点 equation を生成する.

(3) equation を,一方のグループとする.

なお,以下のように多次元正規分布を用いて生成することもできる.

(1) equationを分散共分散行列とする多次元正規分布equationに従うequationを生成する.

(2) equation を,一方のグループとする.

上記で生成された実行可能解の期待値は元問題の目的関数値のequation 倍以上になっていることが知られている([1]).

[参考]
[1] M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problem Using Semidefinite Programming, Journal of the ACM, 42(6), 1115-1145, 1995
[2] Christoph Helmberg, Semidefinite Programming for Combinatorial Optimization, Konrad-Zuse-Zentrum fur Informationstechnik Berlin,January 2000
[3] 松井知己, 半正定値計画を用いた最大カット問題の .878 近似解法, オペレーションズ・リサーチ 経営の科学, 45, (3), 2000, pp.140-145