WEKO3
アイテム
多項式時間決定的サンプラーの頂点誤差解析
https://ipsj.ixsq.nii.ac.jp/records/102910
https://ipsj.ixsq.nii.ac.jp/records/102910ad914627-4761-4276-b9f3-4ed428a6d892
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14149004.pdf (221.9 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-09-05 | |||||||
| タイトル | ||||||||
| タイトル | 多項式時間決定的サンプラーの頂点誤差解析 | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 九州大学 | ||||||||
| 著者所属 | ||||||||
| 九州大学 | ||||||||
| 著者所属 | ||||||||
| 九州大学 | ||||||||
| 著者所属 | ||||||||
| 九州大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu University | ||||||||
| 著者名 |
白髪丈晴
山内由紀子
来嶋秀治
山下雅史
× 白髪丈晴 山内由紀子 来嶋秀治 山下雅史
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | マルコフ連鎖モンテカルロ法 (MCMC 法) とは，マルコフ連鎖をシミュレートすることで所望の分布からサンプリングを行う手法である．本稿ではロータールーターモデル (Propp 機械) など 「ランダムウォークの脱乱択化」 に関する研究を応用し，マルコフ連鎖を模倣する決定的サンプリングアルゴリズムを提案する．そして，決定的サンプリングアルゴリズムと対応するマルコフ連鎖の分布の頂点誤差 (L∞ 距離) の解析を行い，マルコフ連鎖の混交時間に関する上界を与える．この上界を用いて，0-1 ナップサック解，線形順序拡大，マッチングなどの一様分布に急速混交するマルコフ連鎖が知られるいくつかの #P 完全問題に対し，決定的サンプリングアルゴリズムが所望の分布と頂点誤差が ε 以下の分布を，入力と ε-1 の多項式時間で出力する事を示す． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-149, 号 4, p. 1-7, 発行日 2014-09-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
