| 大会名称 |
|---|
| 2020年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2020 |
| 発行日 |
| 2020-08-18 |
| セッション番号 |
| 1a |
| セッション名 |
| モデル・アルゴリズム・コンピュテーション |
| 講演日 |
| 2020/09/01 |
| 講演場所(会議室等) |
| a |
| 講演番号 |
| CA-002 |
| タイトル |
| 構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム |
| 著者名 |
| 伊藤健洋, 垣村尚徳, 神山直之, 小林佑輔, 岡本吉央, |
| キーワード |
| 固定パラメータアルゴリズム, ロバスト最適化, 組合せ最適化, マトロイド |
| 抄録 |
| 本論文では，次のように定義する．新しいロバスト修復可能組合せ最適化問題の研究を行う．すなわち，ランクrのマトロイド M=(E, I) と E の部分集合 E1, ..., Es (ただし，各 Ei のランクは r )，自然数 k が与えられたとき，M の基 B で，各 i に対して，|B ∩ Ei| ≧ r - k を満たすものが存在するか答える問題を考える．これは E1, ..., Es という未来のシナリオに対して即座に対応できるような解 B を見つけるロバスト最適化問題であると捉えられる．本論文の結果は以下の通りである．まず，M が一様マトロイドまたはグラフ的マトロイドであっても，NP完全であることを示す．また，s をパラメータとしたとき，固定パラメータ・アルゴリズムを設計する． |
| 本文pdf |
| PDF download (357.9KB) |