文献

J-GLOBAL ID：201802230268987261   整理番号：18A1027550

4次元までの超体積寄与の計算と更新【JST・京大機械翻訳】

Computing and Updating Hypervolume Contributions in Up to Four Dimensions

著者 (2件)： Guerreiro Andreia P. (Department of Informatics Engineering, Centre for Informatics and Systems, University of Coimbra, Coimbra, Portugal) ,  Fonseca Carlos M. (Department of Informatics Engineering, Centre for Informatics and Systems, University of Coimbra, Coimbra, Portugal)
資料名： IEEE Transactions on Evolutionary Computation  (IEEE Transactions on Evolutionary Computation)
巻： 22  号： 3  ページ： 449-463  発行年： 2018年 
JST資料番号： W0968A  ISSN： 1089-778X  CODEN： ITEVF5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 多目的選択とアーカイブによる接続において,超体積部分集合選択問題(HSSP)は,超体積指標を最大化するd次元空間におけるn非支配点の集合X⊂R~dのサイズk≦nのサブセットを発見することにある。HSSPへの増分グリーディ近似は1-1/eの近似保証を持ち,nとkで多項式であるが,d≧3では多項式厳密アルゴリズムは知られていない。減少gre欲対応物は既知の近似保証を持たないが,大きなkに対しては潜在的に速く,実際には良好な近似をもたらす。個々の超体積寄与の計算と更新は,このgre欲な戦略の実行の中心にある。本論文では,超体積寄与の計算と更新のための新しいアルゴリズムを開発した。三次元において,単一点変化下での全超体積と全個別寄与の更新を線形時間で行い,一方,4Dケースでは全ての寄与をO(n~2)時間で計算した。結果として,HSSPに対する減少gre欲近似は,それぞれd=3およびd=4に対してO(n(n-k)+nlogn)およびO(n~2(n-k))時間で得られる。実験結果は,提案したアルゴリズムが既存のものより著しく優れていることを示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  アルゴリズム ,  近似法 ,  *四次元 ,  三次元 ,  線形性 ,  部分集合
準シソーラス用語： 厳密アルゴリズム ,  部分集合選択 , 【Automatic Indexing@JST】

分類 (1件)： 信号理論  (ND02020G)

タイトルに関連する用語 (4件)： 4次元 ,  体積 ,  計算 ,  更新