Minmax regret bottleneck problems with solution-induced interval uncertainty structure

We consider minmax regret bottleneck subset-type combinatorial optimization problems, where feasible solutions are some subsets of a finite ground set of cardinality nn. The weights of elements of the ground set are uncertain; for each element, an uncertainty interval that contains its weight is given. In contrast with previously studied interval data minmax regret models, where the set of scenarios (possible realizations of the vector of weights) does not depend on the chosen feasible solution, we consider the problem with solution-induced interval uncertainty structure. That is, for each element of the ground set, a nominal weight from the corresponding uncertainty interval is fixed, and it is assumed that only the weights of the elements included in the chosen feasible solution can deviate from their respective nominal values. This uncertainty structure is motivated, for example, by network design problems, where the weight (construction cost, connection time, etc.) of an edge gets some “real” value, possibly different from its original nominal estimate, only for the edges (connections) that are actually implemented (built); or by capital budgeting problems with uncertain profits of projects, where only the profits of implemented projects can take “real” values different from the original nominal estimates. We present a polynomial O(n2)O(n2) algorithm for the problem on a uniform matroid of rank pp, where feasible solutions are subsets of cardinality pp of the ground set. For the special case where the minimum of the nominal weights is greater than the maximum of the lower-bound weights, we present a simple O(n+plogp)O(n+plogp) algorithm.