Upgrading p-Median Problem on a Path

Upgrading p‐median problem is a problem of finding the best median of the given graph through modification of its parameters. The current paper develops a polynomial‐time model to address this problem when the weights of vertices can be varying under a given budget. Moreover, in the case where the considering graph has a special structure, namely a path, a linear time algorithm will be proposed for solving the problem with uniform cost.