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.



Finding Optimal Vertex Weights without Linear Programing
See my recent paper "Maximizing the sum of radii of disjoint balls or disks", J. Computational Geometry 8 (1): 316–339, 2017, <http://doi.org/10.20382/jocg.v8i1a12>, on problems like this. It is the dual of the LP relaxation of a weighted matching problem, and (even though the relaxation allows fractional solutions instead of just 0-1 solutions) it can be solved by graph matching based algorithms.


