  Recoverable robust optimization is a multi-stage approach, where it is
possible to adjust a first-stage solution after the uncertain cost scenario is
revealed. We analyze this approach for a class of selection problems. The aim
is to choose a fixed number of items from several disjoint sets, such that the
worst-case costs after taking a recovery action are as small as possible. The
uncertainty is modeled as a discrete budgeted set, where the adversary can
increase the costs of a fixed number of items. While special cases of this
problem have been studied before, its complexity has remained open. In this
work we make several contributions towards closing this gap. We show that the
problem is NP-hard and identify a special case that remains solvable in
polynomial time. We provide a compact mixed-integer programming formulation and
two additional extended formulations. Finally, computational results are
provided that compare the efficiency of different exact solution approaches.
