ダウンロード数: 49
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.orl.2022.05.001.pdf | 317.89 kB | Adobe PDF | 見る/開く |
タイトル: | A parameterized view to the robust recoverable base problem of matroids under structural uncertainty |
著者: | Ito, Takehiro Kakimura, Naonori Kamiyama, Naoyuki Kobayashi, Yusuke ![]() ![]() ![]() Okamoto, Yoshio |
著者名の別形: | 小林, 佑輔 |
キーワード: | Robust recoverable optimization Fixed-parameter tractability Matroid |
発行日: | May-2022 |
出版者: | Elsevier BV |
誌名: | Operations Research Letters |
巻: | 50 |
号: | 3 |
開始ページ: | 370 |
終了ページ: | 375 |
抄録: | We study a robust recoverable version of the matroid base problem where the uncertainty is imposed on combinatorial structures rather than on weights as studied in the literature. We prove that the problem is NP-hard even when a given matroid is uniform or graphic. On the other hand, we prove that the problem is fixed-parameter tractable with respect to the number of scenarios. |
著作権等: | © 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license. |
URI: | http://hdl.handle.net/2433/279147 |
DOI(出版社版): | 10.1016/j.orl.2022.05.001 |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス