TY - JOUR
T1 - A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
AU - Ito, Takehiro
AU - Kakimura, Naonori
AU - Kamiyama, Naoyuki
AU - Kobayashi, Yusuke
AU - Okamoto, Yoshio
N1 - Funding Information:
The authors thank Christina Büsing for sending us her Ph.D. Thesis [8] . They also thank the referee for detailed comments that improved the presentation. This work is supported by JST PRESTO JPMJPR1753 , JSPS KAKENHI JP17K00028 , JP17K19960 , JP18H04091 , JP18H05291 , JP19H05485 , JP19K11814 , JP20H05793 , JP20H05795 , JP20K11670 , and JP20K11692 , Japan.
Publisher Copyright:
© 2022 The Author(s)
PY - 2022/5
Y1 - 2022/5
N2 - 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.
AB - 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.
KW - Fixed-parameter tractability
KW - Matroid
KW - Robust recoverable optimization
UR - http://www.scopus.com/inward/record.url?scp=85129914807&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85129914807&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2022.05.001
DO - 10.1016/j.orl.2022.05.001
M3 - Article
AN - SCOPUS:85129914807
SN - 0167-6377
VL - 50
SP - 370
EP - 375
JO - Operations Research Letters
JF - Operations Research Letters
IS - 3
ER -