In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, we give an overview over exact solution methods for \NP-hard cases. While mostly concentrating on the classical concept of strict robustness, we also cover more recent two-stage optimization paradigms.
Article
View Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty