このアイテムのアクセス数: 103
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| 2108-09.pdf | 7.07 MB | Adobe PDF | 見る/開く |
| タイトル: | 最小費用全域木ゲームのShapley値に対する近似アルゴリズム (高度情報化社会に向けた数理最適化の新潮流) |
| 著者: | 高瀬, 光一  安藤, 和敏 |
| 著者名の別形: | Takase, Koichi Ando, Kazutoshi |
| 発行日: | Apr-2019 |
| 出版者: | 京都大学数理解析研究所 |
| 誌名: | 数理解析研究所講究録 |
| 巻: | 2108 |
| 開始ページ: | 95 |
| 終了ページ: | 114 |
| 抄録: | 最小費用全域木ゲームはそれを定義するネットワークの費用関数が木距離である場合には木距離最小費用全域木ゲームと呼ばれる. 一般の最小費用全域木ゲームのShapley値の計算は#P-困難であるが, 木距離最小費用全域木ゲームのShapley値は多項式時間で計算できることが知られている. 本研究では, 木距離最小費用全域木ゲームに対する多項式時間アルゴリズムのアイデアに基づいて, 一般の最小費用全域木ゲームのShapley値に対する多項式時間近似アルゴリズムを導入した. このアルゴリズムの近似精度を評価するためにランダムに生成した費用関数を入力として数値実験を行った結果, 与えられた費用関数が2次元ユークリッド距離の場合には最大でも14%程度の相対誤差を持つということが観察された. |
| URI: | http://hdl.handle.net/2433/251924 |
| 出現コレクション: | 2108 高度情報化社会に向けた数理最適化の新潮流 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。