Robust recoverable and two-stage selection problems
Adam Kasperski, Paweł Zieliński · Discrete Applied Mathematics · 2017
In this paper the following selection problem is discussed. A set of n items is given and we wish to choose a subset of exactly p items of the minimum total cost. This problem is a special case of 0–1 knapsack in which all the item weights are equal to 1. Its deterministic version has an O(n)-time algorithm, which consists in choosing p items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided.