  In this work we investigate the min-max-min robust optimization problem and
the k-adaptability robust optimization problem for binary problems with
uncertain costs. The idea of the first approach is to calculate a set of k
feasible solutions which are worst-case optimal if in each possible scenario
the best of the k solutions is implemented. It is known that the min-max-min
robust problem can be solved efficiently if k is at least the dimension of the
problem, while it is theoretically and computationally hard if k is small.
However, nothing is known about the intermediate case, i.e. k lies between one
and the dimension of the problem. We approach this open question and present an
approximation algorithm which achieves good problem-specific approximation
guarantees for the cases where k is close to or where k is a fraction of the
dimension. The derived bounds can be used to show that the min-max-min robust
problem is solvable in oracle-polynomial time under certain conditions even if
k is smaller than the dimension. We extend the previous results to the robust
k-adaptability problem. As a consequence we can provide bounds on the number of
necessary second-stage policies to approximate the exact two-stage robust
problem. We derive an approximation algorithm for the k-adaptability problem
which has similar guarantees as for the min-max-min problem. Finally, we test
both algorithms on knapsack and shortest path problems and related two-stage
variants. The experiments show that both algorithms calculate solutions with
relatively small optimality gap in seconds.
