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 NP‐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.