部分集合分解による近似アルゴリズムの改良について
スポンサーリンク
概要
- 論文の詳細を見る
部分集合分解という手法を用いた, 最大カット問題に対する近似アルゴリズムについて述べる. 部分集合分解アルゴリズムは他の近似アルゴリズムと組み合わせて用いることにより, そのアルゴリズムにより出力された解を改善することが期待できる. 計算機実験による結果によれば, 単純な貧欲法と組み合わせて用いた場合, 貧欲法により得られたカットの枝数を多くの場合増加させ, 最大で10%程度増加させることができた.
- 社団法人電子情報通信学会の論文
- 1996-11-22
著者
関連論文
- 密な部分グラフ問題の貪欲解法
- 部分集合分解による近似アルゴリズムの改良について
- CRCW PRAMの時間計算量の稠密な階層
- テープ記号数を制限した領域限定TMの階層について
- トーラス上の局所多数決と大域多数決
- 指数個の決定性状態を必要とする非決定性有限オートマトンについて(計算理論とその応用)