The balanced p-maxian problem on a tree

In this paper we consider the balanced p-maxian problem on a tree graph. In this problem two objective function are considered. The first one is the traditional p-maxian problem and the second one is minimizing the maximum demand that allocated to any facility. In the case p=2, we show that the optimal solution is two end vertices of the diameter of the tree. Based on this property an ?O(??n2) algorithm is presented to solve the balanced 2-maxian problem.

Keywords:

P-maxian Problem , Balanced Allocation , Facility Location