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.