On a constant factor approximation for minmax regret problems using a symmetry point scenario

In order to find a robust solution under an unknown linear cost function it will be considered the minmax regret criterion. It is assumed the vector of costs can take on values from a given uncertainty set. The resulting optimization model has been extensively analyzed in the literature when the uncertain costs are modeled by closed intervals. Unfortunately, except for rare applications, this problem has NPNP-hard complexity which has led to the appearance of approximated methods seeking for good solutions in a short computational time.The most recent approaches solve the deterministic version of the optimization problem under the midpoint scenario, that realization in which each cost takes the midpoint of the closed interval. Proceeding in this way it can be obtained a 2-approximation for a wide class of minmax regret optimization models. In this paper it is shown how this approach can be extended to a new class of minmax regret problems including more general uncertainty sets.

► We study a minmax regret optimization problem with costs belonging to a general set. ► A new approximation to the optimal solution and a bound for its error are obtained. ► This approximation is the optimal solution under the symmetry point cost scenario. ► Moreover, a new concept called α-approximator is introduced. ► Using this tool one can refine the constant factor of the approximation.