Backup reverse 2-median problem on trees

In this paper we consider the reverse of backup 2-median problem with varying in edges of graph. In this problem a set of weighted points are given and we should change some parameters of problem such as weights of vertices and edges and coordinates of points such that the two given points be the backup 2-median. In a reverse optimization problem, we are given a budget for modifying parameters of the problem. The goal is to modify parameters of the problem such that an objective function attains its best possible value subject to the given budget. it was assumed that the vertex weights are positive. Since the problem is NP-hard on general graphs, different other special graph classes should be investigated. We have shown that the backup reverse 2-median problem is equivalent in the sense that it can be transformed to a backup reverse 2-median problem on a path.

Keywords:

Reverse Optimization , Backup 2-Median , Location