First, we introduce the instance of the problem. Let G = (V, E) be a
connected graph with the vertex set V (|V | = n) and the edge set E. Each
edge e ∈ E has a positive length le and each vertex v ∈ V has a positive
weight w. Moreover, let d(v, v′) denote the shortest distance between two
vertices v, v′ ∈ V. It is allowed to change the vertex weights. Increasing and
decreasing each w by one unit imposes us costs cv and cv′, respectively. A
budget B is also assigned in order to change the vertex weights. Let xv ≥ 0
be the amount by which the weight w is increased and y be the amount
by which the weight w is decreased.