On the complexity of determining tolerances for ->e--optimal solutions to min-max combinatorial optimization problems

Sensitivity analysis of e-optimal solutions is the problem of calculating the range within which a problem parameter may lie so that the given solution re-mains e-optimal. In this paper we study the sensitivity analysis problem for e-optimal solutions tocombinatorial optimization problems with min-max ob-jectives where e > 0. We show that the problem is easy if the original problem is easy. We also show that the converse is true under the assumption that it is possible to calculate an e-optimal solution to the problem in polynomial time.