Robust optimization is a popular approach for modeling and solving optimization problems with uncertain data. Most studies in that field consider that the flow of information revealed during the decision stages is independent of the decision. Instead, here we consider that a part of the decision variables controls that flow. The decision-dependent information discovery (DDID) approach applies to many real-world applications, such as production planning where the production cost of a type of item is revealed after having taken the decision to produce it. The knowledge of that cost then contributes to deciding how many items of that type should be produced.

The research field of robust problems with DDID is recent, and mainly focuses on exact and approximate methods to solve them numerically. In this work, more focused on theory, we study the complexity of the robust selection problem with DDID under budgeted uncertainty. In particular, we present polynomial complexity results for two special cases of this problem and extend the second one to a broader class of problems.