Robust vertex centdian facility location problem on tree networks

This paper studies the robust vertex centdian location problem on tree networks with interval edge lengths. To obtain a robust solution, we use the minmax regret criterion. First, we obtain atmost n worst case scenario for each pair of vertices on tree networks. Then we reduce this number to \( \log n \) $logn$ . Finally, the total time for obtaining a robust solution is equal to \( O(n^{4}) \) $O(n^4)$ . This time is reduced to \( O(n^{3}\log n) \) $O(n^{3}logn)$ by using the property of binary search tree and weighted centroid.