zbMATH — the first resource for mathematics

The complexity analysis of the inverse center location problem. (English) Zbl 0978.90065
Summary: 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.

90B80 Discrete location and assignment
90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX Cite
Full Text: DOI