誘導部分グラフで閉じられた固定パラメータ扱い可能グラフ問題のための焦点ジャンプおよび修復制約処理【JST・京大機械翻訳】

Branson Luke; Sutton Andrew M.

プレプリント

J-GLOBAL ID：202202217536773286 整理番号：22P0310527

誘導部分グラフで閉じられた固定パラメータ扱い可能グラフ問題のための焦点ジャンプおよび修復制約処理【JST・京大機械翻訳】

Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems Closed Under Induced Subgraphs

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年03月25日プレプリントサーバーでの情報更新日： 2023年01月20日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

修復演算子は制約付き組合せ最適化における制約処理にしばしば用いられる。グラフ問題において確率的に実行不可能な子孫を確率的に修復するために使用できる,調整されたジャンプおよび修復操作を備えた(1+1) ̄EAを研究した。全体のグラフに対する候補解を進化させる代わりに,著者らは,(1+1) ̄EAが,実例(誘導部分グラフ)の成長する部分集合と共に,並列に実行可能な解法を開発するように,遺伝子型を拡大した。このアプローチにより,EAは古典的固定パラメータアルゴリズムで用いられる反復圧縮プロセスを確率的にシミュレートでき,3つのNP-ハードグラフ問題に関するランダム化FPT性能保証を得ることを証明した。k-VertexCoverでは,集束ジャンプおよび修理を用いた(1+1)EAが,期待値におけるO(2 ̄kn ̄2logn)反復においてk-頂点カバー(もし1つが存在する)を見つけることができることを証明した。これは,VertexCover上の進化アルゴリズムに対して,既知のパラメータ化限界よりも指数的(k)改善をもたらす。トーナメントにおけるk-フィードバックVertexSet問題に対して,EAは期待値におけるO(2 ̄k_k≦n ̄2log_n)反復において実現可能なフィードバックセットを見出し,OddCycle Transversalに対しては,EAに対する最適化時間はO(3 ̄k k m ̄n ̄2logn)であることを証明した。後者の2つの問題に対して,これは任意の進化的アルゴリズムに対する最初のパラメータ化結果を構成する。誘導部分グラフの下で閉じた他のパラメータ化グラフ問題に対するフレームワークを一般化する方法を議論し,具体的インスタンスクラス上のアルゴリズムの挙動を説明する実験結果を報告した。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

グラフ理論基礎 , 計算理論

, , , , , , ,

前のページに戻る