Are there algorithms for finding $\omega_1\dots,\omega_n$, so that

$\omega_i+\omega_j\le \|e_{ij}\|\ \forall i,j\quad\wedge\quad\sum{\omega_i}=max$

that are *not* based on linear programing, e.g. graph theoretic algorithms?

Remark:

the number of constraints in the $LP$ formulation can be reduced on basis of the following observation:

let $\mu_i$ be the mimimum of the weights of edges, that are adjacent to vertex $v_i$ (in the graph interpretation of the problem); then $\omega_i+\omega_j \le \mu_i+\mu_j$ (because of the non-negativity constraints) and edges, for which $\|e_{ij}\|\ge\mu_i+\mu_j$ trivially satisfy $\|e_{ij}\|\le\omega_i+\omega_j$ which implies, that the respective constraint need not be included in the $LP$ formulation.

The impact of that reduction can be increased in some cases by subtracting from all edge weights the weight of the shortest edge and adding it to the $\omega_i'$ constituting to the solution of the modified problem.