A parameterized view to the robust recoverable base problem of matroids under structural uncertainty

[1] D. Adjiashvili, S. Stiller, R. Zenklusen, Bulk-robust combinatorial optimization,

Math. Program. 149 (1–2) (2015) 361–390.

[2] H. Aissi, C. Bazgan, D. Vanderpooten, Pseudo-polynomial algorithms for minmax and min-max regret problems, in: Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13,

2005 Proceedings, 2005, pp. 171–178.

[3] H. Aissi, C. Bazgan, D. Vanderpooten, Approximation of min-max and min-max

regret versions of some combinatorial optimization problems, Eur. J. Oper. Res.

179 (2) (2007) 281–290.

[4] H. Aissi, C. Bazgan, D. Vanderpooten, Min-max and min-max regret versions of

combinatorial optimization problems: a survey, Eur. J. Oper. Res. 197 (2) (2009)

427–438.

´ The recoverable robust facility loca[5] E. Álvarez-Miranda, E. Fernández, I. Ljubic,

tion problem, Transp. Res., Part B, Methodol. 79 (2015) 93–120.

[6] E. Álvarez-Miranda, I. Ljubic, S. Raghavan, P. Toth, The recoverable robust twolevel network design problem, INFORMS J. Comput. 27 (1) (2015) 1–19.

[7] I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty, Math. Program. 90 (2) (2001) 263–272.

[8] C. Büsing, Recoverable Robustness in Combinatorial Optimization, PhD thesis,

Technical University of Berlin, 2010.

[9] C. Büsing, Recoverable robust shortest path problems, Networks 59 (1) (2012)

181–189.

[10] C. Büsing, A.M.C.A. Koster, M. Kutschka, Recoverable robust knapsacks: the discrete scenario case, Optim. Lett. 5 (3) (2011) 379–392.

[11] M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M.

Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, 2015.

[12] D. Dadush, C. Peikert, S. Vempala, Enumerative lattice algorithms in any norm

via M-ellipsoid coverings, in: Proceedings of the 52nd Annual Symposium on

Foundations of Computer Science, 2011, pp. 580–589.

[13] D. Dadush, S. Vempala, Deterministic construction of an approximate Mellipsoid and its applications to derandomizing lattice algorithms, in: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012,

pp. 1445–1456.

Reference in supplementary material

[27] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, in: The IBM Research Symposia Series, 1972, pp. 85–103.

375

...