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.
ASJC Scopus subject areas
- 経営科学およびオペレーションズ リサーチ