慶應義塾大学学術情報リポジトリ(KOARA)KeiO Associated Repository of Academic resources

慶應義塾大学学術情報リポジトリ(KOARA)

ホーム  »»  アイテム一覧  »»  アイテム詳細

アイテム詳細

アイテムタイプ Article
ID
2018000005-20180249  
プレビュー
画像
thumbnail  
キャプション  
本文
2018000005-20180249.pdf
Type :application/pdf Download
Size :117.4 KB
Last updated :Oct 24, 2022
Downloads : 136

Total downloads since Oct 24, 2022 : 136
 
本文公開日
 
タイトル
タイトル 劣モジュラ性を持つ組合せ最適化問題に対する実用的高速なアルゴリズム  
カナ レツモジュラセイ オ モツ クミアワセ サイテキカ モンダイ ニ タイスル ジツヨウテキ コウソクナ アルゴリズム  
ローマ字 Retsumojurasei o motsu kumiawase saitekika mondai ni taisuru jitsuyōteki kōsokuna arugorizumu  
別タイトル
名前 Efficient algorithms for combinatorial optimization problems with submodularity  
カナ  
ローマ字  
著者
名前 垣村, 尚徳  
カナ カキムラ, ナオノリ  
ローマ字 Kakimura, Naonori  
所属 慶應義塾大学理工学部准教授  
所属(翻訳)  
役割 Research team head  
外部リンク  
 
出版地
 
出版者
名前 慶應義塾大学  
カナ ケイオウ ギジュク ダイガク  
ローマ字 Keiō gijuku daigaku  
日付
出版年(from:yyyy) 2019  
出版年(to:yyyy)  
作成日(yyyy-mm-dd)  
更新日(yyyy-mm-dd)  
記録日(yyyy-mm-dd)  
形態
1 pdf  
上位タイトル
名前 学事振興資金研究成果実績報告書  
翻訳  
 
 
2018  
 
開始ページ  
終了ページ  
ISSN
 
ISBN
 
DOI
URI
JaLCDOI
NII論文ID
 
医中誌ID
 
その他ID
 
博士論文情報
学位授与番号  
学位授与年月日  
学位名  
学位授与機関  
抄録
劣モジュラ性は組合せ最適化における基本的な概念の一つであり、効率的に計算できる組合せ最適化問題の多くに現れる性質である。劣モジュラ関数を最大化する問題は文書要約やクラスタリングなど多くの応用を持つことから、機械学習や知識発見など情報科学分野で注目を集め、これまでに様々な計算手法が提案されてきた。しかし、これらの応用では大規模なデータを扱う必要があり、メモリサイズや計算時間の両面において従来の計算手法では解決できない困難な状況が生じている。
本研究課題では、基本的な制約の下で劣モジュラ関数を最大化する問題に対して、入力データを全て保持せずに計算するストリーミング計算手法を設計した。提案アルゴリズムは入力データを定数回しか見ずに効率的に近似解を計算するものであり、メモリ効率が高くデータが大規模な場合に有用である。まず、サイズ制約のもと劣モジュラ関数を最大化する問題に対して(1-1/e)近似解を計算する手法を提案した。この近似比率は理論的に最適であり、計算時間も従来手法より高速である。さらに、ナップサック制約付の問題について初めて非自明な近似比解析を与えた。この成果は、フランス・パリのENSのChien-Chung Huang氏との共同研究である。情報処理学会のアルゴリズム研究会で口頭発表を行ない、査読付論文誌に投稿中である。
上記の結果の他にも、RIKEN AIP宮内敦史氏との共同研究によって、劣モジュラ構造を利用したコミュニティ検出問題に対する新しいモデルと解法の提案を行なった。これは、CIKMという知識発見分野の査読付国際会議に採択されている。
Submodularity is one of the most important notion in combinatorial optimization. It is known that submodularity appears in many efficiently-solvable combinatorial optimization problems. Recently, submodular functions have attracted much attention in machine learning and knowledge discovery. In particular, the problem of maximizing submodular functions has been studied extensively because it has many practical applications such as text summarization and clustering. Although there are efficient algorithms for the problem, in such practical applications, we face difficulties in space complexity and computational time, as we have to manage huge input data and we cannot store every input data on RAM.
In this project, we focus on the problem of maximizing submodular functions under fundamental constraints, and design efficient streaming algorithms for the problem. Our proposed algorithms read the input data only a constant number of times, and are effective in space as the space required is independent of the input data size. Specifically, we propose a streaming algorithm that finds a (1-1/e)-approximate solution for the cardinality-constrained problem. This approximation ratio is theoretically optimal, and it runs faster than the previous algorithms. Moreover, we design the first streaming algorithm that finds a nontrivial-ratio-approximate solution for the knapsack-constrained problem. This is joint work with Chien-Chung Huang in ENS Paris. We gave a talk on this result in Workshop on Algorithms held by Special Interest Group on Algorithms (SIGAL) of Information Processing Society of Japan (IPSJ), and a journal version was submitted.
Besides, we propose a new optimization model with submodular structure for detecting a community in a social network, which is a collaboration with Atsushi Miyauchi from RIKEN AIP, and this result is published in the refereed conference on knowledge discovery named CIKM.
 
目次

 
キーワード
 
NDC
 
注記

 
言語
日本語  

英語  
資源タイプ
text  
ジャンル
Research Paper  
著者版フラグ
publisher  
関連DOI
アクセス条件

 
最終更新日
Oct 24, 2022 13:38:11  
作成日
Oct 24, 2022 13:38:11  
所有者
mediacenter
 
更新履歴
Oct 24, 2022    インデックス を変更
 
インデックス
/ Public / 塾内助成報告書 / 学事振興資金研究成果実績報告書 / 2018年度
 
関連アイテム
 

ランキング

最も多く閲覧されたアイテム
1位 慶應義塾大学日吉... (1014) 1st
2位 「危険の予見可能... (594)
3位 731部隊と細菌戦 ... (390)
4位 新自由主義に抗す... (390)
5位 ガールクラッシュ... (359)

最も多くダウンロードされたアイテム
1位 アセトアニリドの... (966) 1st
2位 731部隊と細菌戦 ... (773)
3位 酢酸エステル類の... (714)
4位 渋沢栄一と朝鮮 :... (700)
5位 慶應義塾大学日吉... (657)

LINK

慶應義塾ホームページへ
慶應義塾大学メディアセンターデジタルコレクション
慶應義塾大学メディアセンター本部
慶應義塾研究者情報データベース