Up- and downgrading the 1-center in a network

We study budget constrained network improvement and degrading problems based on the vertex 1-center problem on graphs: given a graph with vertex weights and edge lengths the task is to decrease and increase the vertex weights within certain limits such that the optimal 1-center objective value with respect to the new weights is minimized and maximized, respectively. The upgrading (improvement) problem is shown to be solvable in O(n2)O(n2) time provided that the distance matrix is given. The downgrading 1-center problem is shown to be strongly NPNP-hard on general graphs but can be solved in O(n2)O(n2) time on trees. As byproduct we suggest an algorithm that solves the problem of minimizing over the upper envelope of n   piecewise linear functions in O(K+n)O(K+n) time where K is the total number of breakpoints.