Minmax and minmax regret versions of combinatorial optimization problems: A survey
Minmax and minmax regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the minmax and minmax regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min st cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.
minmax minmax regret combinatorial optimization robustness complexity approximation