Improved polynomial algorithms for robust bottleneck problems with interval data

摘要

To model uncertainties in a problem one can provide intervals of uncertainty specifying a range for eachrnuncertain parameter value. To hedge against 'worst-case scenarios', i.e., most unwelcome realizations ofrnthe uncertain parameters after a solution has been determined, the minmax-regret criterion has beenrnadopted in robust optimization. Within this field, we consider bottleneck problems with one or morernuncertain parameter functions.rnWe apply a known polynomial time solution scheme for a number of specific problems of this type withrnone uncertain parameter function. This leads to improved algorithms of reduced complexity, e.g., for thernbottleneck Steiner tree problem and the bottleneck assignment problem.rnFurther, we formulate a framework to solve single machine scheduling problems in polynomial timernunder the maximum tardiness criterion, with up to three uncertain parameter functions.