Semi-obnoxious backup ۲-median problem on a tree

In this paper, we discuss the obnoxious and semi-obnoxious version of the backup ۲-median problem on a tree. In the obnoxious case of the ۲-median problem, all vertices have negative weights, whereas in the semi-obnoxious model the vertices may have either positive or negative weights. In these two problems, we should find the location of two facility servers on the tree so that the sum of minimum weighted distances from vertices in the tree to the set of functioning servers is minimized. In the backup model, each facility server may probably fail. If a facility server fails, the remaining server should serve the clients. Vertex optimality is an important property for the ۲-median problem. This property indicates that the set of vertices involves an optimal solution of the ۲-median problem. We verify that the vertex optimality holds for the semi-obnoxious backup ۲-median problem on a tree network. In the obnoxious ۲-median problem, the set of leaves contains an optimal solution, we show that this property does not hold for the obnoxious backup ۲-median problem.

کلیدواژه ها:

۲-median ، backup ، obnoxious ، semi-obnoxious ، positive and negative weight