The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.