文献

J-GLOBAL ID：201902272630879378   整理番号：19A2879892

近似サブモジュラ関数最大化のための効率的な分枝切断アルゴリズム【JST・京大機械翻訳】

An Efficient Branch-and-Cut Algorithm for Approximately Submodular Function Maximization

著者 (3件)： Uematsu Naoya (Osaka University,Center for Advanced Intelligence Project (AIP), RIKEN, and Graduate School of Information Science and Technology) ,  Umetani Shunji (Osaka University, and Center for Advanced Intelligence Project (AIP), RIKEN,Graduate School of Information Science and Technology) ,  Kawahara Yoshinobu (Institute of Mathematics for Industry (IMI), Kyushu University, and Center for Advanced Intelligence Project (AIP), RIKEN)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2019  号： SMC  ページ： 3160-3167  発行年： 2019年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 計算機科学における問題に近づくとき,著者らはしばしば,いくつかの効用関数を最大化する有限集合の部分集合が選択される必要がある状況に遭遇する。このような効用関数のいくつかは近似的にサブモジュールであることが知られている。近似的なサブモジュール関数(ASFM問題)を最大化する問題に対して,gre欲なアルゴリズムは,与えられたサブモジュラー比γに対する(1-e-γ)近似比を保証しながら,多くの事例に対して良好な実行可能な解を迅速に見出す。しかしながら,著者らは,合理的な計算時間内でより正確で正確な最適解を求める応用に遭遇している。本論文において,著者らは,制約の指数関数的数を有するその二値整数計画法(BIP)定式化に基づく非減少ASFM問題のための効率的分枝限定アルゴリズムを提示した。この目的のために,最初にASFM問題のBIP定式化を導き,次に,各反復における制約の有望な集合を追加しながら,制約の小さい部分集合を持つ低減BIP問題から始まる改良制約生成アルゴリズムを開発した。さらに,探索木の少数のノードを解きながら,良好な上限を達成するために,分枝限定アルゴリズムにそれを組み込んだ。3つのタイプのよく知られたベンチマーク例に対する計算結果は,著者らのアルゴリズムが従来の正確なアルゴリズムよりも優れていることを示した。Copyright 2019 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ベンチマーク ,  定式化 ,  分枝限定法 ,  *アルゴリズム ,  効用関数 ,  部分集合 ,  計算機科学 ,  整数計画法 ,  *近似法 ,  指数関数 ,  探索木 ,  最適解

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (6件)： 近似 ,  サブ ,  関数 ,  最大化 ,  分枝 ,  アルゴリズム