Minmax regret solutions for minimax optimization problems with uncertainty

We propose a general approach for finding minmax regret solutions for a class of combinatorial optimization problems with an objective function of minimax type and uncertain objective function coefficients. The approach is based on reducing a problem with uncertainty to a number of problems without uncertainty. The method is illustrated on bottleneck combinatorial optimization problems, minimax multifacility location problems and maximum weighted tardiness scheduling problems with uncertainty.