On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given.