  We consider robust counterparts of uncertain combinatorial optimization
problems, where the difference to the best possible solution over all scenarios
is to be minimized. Such minmax regret problems are typically harder to solve
than their nominal, non-robust counterparts. While current literature almost
exclusively focuses on simple uncertainty sets that are either finite or
hyperboxes, we consider problems with more flexible and realistic ellipsoidal
uncertainty sets. We present complexity results for the unconstrained
combinatorial optimization problem and for the shortest path problem. To solve
such problems, two types of cuts are introduced, and compared in a
computational experiment.
