On the complexity of a class of combinatorial optimization problems with uncertainty (Q5935709)

One way of dealing with combinatorial optimization problems with uncertainty in the input data is a worst case approach: one is looking for a solution that performs well for all scenarios. The minimax regret (or robust) version of the worst case approach minimizes the worst case loss in the objective function which occurs since one does not know which scenario will take place. There are two ways to represent scenarios: either a finite set of scenarios is given explicitly by listing the corresponding values of the parameters or an interval of uncertainty is specified for each parameter. The authors show that the robust version of finding a minimum weight base in a uniform matroid is NP-hard in the case the scenarios are represented explicitly by a finite set, but polynomially solvable in the case of an interval representation of the scenarios. Let the uniform matroid of rank \(p\) be defined on a ground set of cardinality \(m\) and let intervals for the weights be given. For this case the author states an \(O((\min (p, m-p))^2m)\) algorithm for finding a robust solution.