講演名	2014/11/13 組み合わせ論的MTS問題(グラフ,ペトリネット,ニューラルネット及び一般) 中薗 拓巳, 畑埜 晃平, 瀧本 英二,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	メトリカルタスクシステム(Metrical Task System)問題(以下,MTS問題)とは,逐次的な意思決定過程をモデル化したもので,ある固定された距離空間(C,δ)を決定空間とするプロトコルとして,次のように記述される.各時刻t=1,2,...,Tにおいて,プレイヤーは損失関数l_t→R_+を観測したあとある決定c_t∈Cを選択し,損失l_t(c_t)+δ(C_t,C_)を被る.プレイヤーの目標は,累積損失に関する競合比を最小化することである.各時刻の計算時間が決定空間のサイズn=|C|に比例するアルゴリズムがいくつか提案されている.しかし,ルーティングやランキングなど多くの問題は,決定空間が組み合わせ論的に定義された指数サイズの問題として定式化されるため,従来手法はそのままでは効率が悪い.例えばルーティング問題では,ある固定されたグラフの全域木の集合が決定空間になるが,そのサイズnは一般にグラフのサイズに関して指数的である.本研究では,c≠c'のときδ(c,c')=1を満たす一様距離空間上のMTS問題を,決定空間C上のサンプリングの問題に還元する手法を提案する.すなわち,効率の良いサンプリングアルゴリズムが存在する決定空間0に対して,MTS問題を効率よく解くことができる.実際,全域木の集合やs-t道の集合など,いくつかの組み合わせ論的な決定空間は,効率の良いサンプリングアルゴリズムを持つことを示す.本手法の競合比の上界は6eln nで,従来手法の競合比O(log n)と同じオーダーを達成している.
抄録(英)
キーワード(和)	重み付きマーキングアルゴリズム /ー様距離空間 / メトリカルタスクシステム
キーワード(英)
資料番号	Vol.2014-AL-150 No.7
発行日

研究会情報
研究会	MSS
開催期間	2014/11/13(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Mathematical Systems Science and its applications(MSS)
本文の言語	JPN
タイトル（和）	組み合わせ論的MTS問題(グラフ,ペトリネット,ニューラルネット及び一般)
サブタイトル（和）
タイトル（英）
サブタイトル（和）
キーワード(1)（和/英）	重み付きマーキングアルゴリズム /ー様距離空間
キーワード(2)（和/英）	メトリカルタスクシステム
第 1 著者 氏名（和/英）	中薗 拓巳
第 1 著者 所属（和/英）	九州大学システム情報科学研究府情報学専攻
第 2 著者 氏名（和/英）	畑埜 晃平
第 2 著者 所属（和/英）	九州大学システム情報科学研究院情報学部門
第 3 著者 氏名（和/英）	瀧本 英二
第 3 著者 所属（和/英）	九州大学システム情報科学研究院情報学部門
発表年月日	2014/11/13
資料番号	Vol.2014-AL-150 No.7
巻番号（vol）	vol.114
号番号（no）	313
ページ範囲	pp.-
ページ数	6
発行日