In the field of robust optimization uncertain data is modeled by uncertainty sets, i.e. sets which contain all relevant outcomes of the uncertain parameters. The complexity of the related robust problem depends strongly on the shape of the uncertainty set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper we introduce a new uncertainty class which is a combination of both. More precisely we consider ellipsoidal uncertainty sets with the additional restriction that at most $\Gamma$ many uncertain parameters may differ from the ellipsoid-center at the same time. We define a discrete and a convex variant of the latter set and prove that the corresponding robust min-max problem is \NP-hard for several combinatorial problems. Furthermore we prove that for uncorrelated budgeted-ellipsoidal uncertainty the min-max problem can be solved in polynomial time for several combinatorial problems if the parameter $\Gamma$ is fixed.
Citation
Department for Mathematics, TU Dortmund University, Vogelpothsweg 87, 44227 Dortmund, Germany