Nina and Avrim's problem

Nina just told me a nice approximation algorithms problem she has written about with Avrim -- "Graph Vertex Pricing".

Stripping out the econ motivation, the problem is as follows:

Input: an undirected graph with nonnegative weights $w(u,v)$ on the edges.

Output: a nonnegative "price" $p\left(v\right)$ on each vertex.

Value: For each edge $(u,v)$ such that $p\left(u\right)+p\left(v\right)\le w(u,v)$, you gain $p\left(u\right)+p\left(v\right)$. Otherwise you gain $0$ for that edge.

Determining $Opt$ is NP-hard, and it's also known [Guruswami-Hartline-Karlin-Kempe-Kenyon-McSherry] to be "APX-hard"; i.e., there is no PTAS unless P = NP.


Nina and Avrim have a paper giving a factor-$4$ approximation algorithm (among many other things). You might want to see if you can think of this algorithm yourself (hint: reduce to the bipartite case; lose a factor of 2 twice).


This seems to me like a very nice problem to work on -- improving either the algorithm or the hardness. One tricky aspect of it is that no one can think of a LP relaxation...