Calculating vertex weights

Question

Vertex weights are a metaphor for a constant value $\pi_i$ that is added to the weight of every edge $e_{ij}$ that is adjacent to vertex $v_i$ in a symmetric graph $G(V,E)$ with weighted edges.

The fact that the edge-set of the optimal tour through the vertices of such a graph is invariant under the addition of vertex weights is exploited in the calculation of the Held Karp lower bound for the Traveling Salesman Problem, but apart from that I couldn't find any other algorithms in graph theory that utilize vertex weights.

As all the edge-set of optimal-weight solutions to problems with predefined nominal vertex-degrees are invariant under the additon of vertex weights, it appears to me that the potential of vertex weights hasn't yet been anticipated by algorithm designers.

Questions:

• what are examples of algorithms in graph theory that yield improved quality of approximate solutions by means of vertex weights?
• are there any publications whose primary subject is the study of vertex weights?

The reason for asking is that I found a way to remove vertex weights from a graph, resp. calculate their value and from experiments I found that the tours reported by heuristics were often up 1% or 2% better after the vertex weights had been removed.

Answer 1

Perfect matchings also have such a degree constraint. So-called "primal-dual algorithms" for network optimization problems use edge variables in the primal problem and node variables (what you are calling "vertex weights") or "dual multipliers" in the dual problem and exploit complementary slackness to iterate between the two until an optimal primal-dual pair of solutions is found. As in general linear programming, every feasible solution to the dual problem provides a bound on the optimal objective of the primal problem, so you get a measure of the optimality gap at every step of the algorithm, with a gap of $0$ indicating optimality.