Pinpointing the complexity of the interval min–max regret knapsack problem

We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.