文献

J-GLOBAL ID：202002235133932172   整理番号：20A1202654

動的重み付き頂点被覆問題に対するRLSおよび(1+1)EAの実行解析【JST・京大機械翻訳】

Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problem

著者 (3件)： Pourhassan Mojgan (Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia) ,  Roostapour Vahid (Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia) ,  Neumann Frank (Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 832  ページ： 20-41  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,進化的アルゴリズムの挙動に関する理論的解析とその二重定式化に基づく動的頂点被覆問題に対するランダム化探索アルゴリズムを実行した。動的頂点被覆問題は既に理論的に研究されており,可能な解を表すための二重定式化を用いることにより,より良い近似挙動を導くことができることが示されている。既存の結果のいくつかを改善した。すなわち,(1+1)EAに対する線形期待再最適化時間を見出し,エッジがグラフから動的に削除されるとき,2近似を再発見する。さらに,動的変化が確率PDにより各ステップで起こる問題に対する動的性を適用するための異なる設定を検討した。また,これらの解析を重み付き頂点被覆問題に拡張し,その中で重みを頂点に割り当て,目標は最小全重みを持つカバー集合を見出すことである。古典的な場合と同様に,重み付き頂点被覆問題に関して考察する動的変化は,グラフからエッジを加えて除去する。頂点被覆問題に対する2近似解を与える双対問題に対する最大解を見出すことを目的とした。これは古典的頂点被覆問題に対する最大マッチング問題と等価である。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 最適化 ,  双対問題 ,  近似法 ,  線形性 ,  *被覆問題 ,  定式化 ,  近傍探索法
準シソーラス用語： 進化的アルゴリズム ,  探索アルゴリズム ,  組合せ最適化 ,  近似解 ,  *頂点被覆 , 【Automatic Indexing@JST】

著者キーワード (5件)： 動的頂点被覆問題 ,  重み付き頂点被覆問題 ,  局所探索 ,  (1+1)EA ,  組合せ最適化

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 頂点被覆 ,  解析