logo IMB
Back

Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

Robust decision-dependent information discovery is harder than robust optimization

Xiaoyu Chen

( LIRMM-Montpellier )

Salle 2, IMB

November 12, 2026 at 11:00 AM

We consider a four-stage variant of robust optimization with cost uncertainty described by the budget uncertainty polytope, known as decision-dependent information discovery (DDID), in which the decision maker first queries a subset of the cost coefficients. The adversary responds by revealing worst-case values for the queried elements, after which the decision maker chooses a feasible solution while facing the remaining uncertainty on the unqueried costs. Our contribution is twofold. On the negative side, we prove that the problem is NP-complete even when the underlying nominal problem is the 2-selection problem, for which only a polynomial number of feasible solutions exist. On the positive side, we prove that the more general p-selection problem can be solved in polynomial time under the additional assumption that all deviations are equal.