Stability Radius and an Upgrading Model of Median Location on Trees

The single median facility location problem seeks to determine an optimal location to minimize the total weighted distance to existing demand points. However, in real-world scenarios, this optimal location can vary due to uncertainty of input data. In such situations, one can measure the robustness of the median location using stability radius, a concept in sensitivity analysis. In this paper, we first show that the stability radius of median location on tree admits a simple and tight lower bound. Furthermore, we investigate an upgrading model for this lower bound by adjusting vertex weights of the tree network within a specified budget. We also introduce a combinatorial approach capable of solving this problem efficiently.