# Labeling nodes in a bipartite graph to satisfy edge constraints

I'm trying to find an algorithm for the following problem. Let $$G$$ be a bipartite graph. The edges in $$G$$ have labels $$R$$; each label $$R(u, v)$$ is an integer range $$[a, b]$$ with $$a$$ and $$b$$ being nonnegative integers with $$a \le b$$. The problem is to assign each node in the graph with nonnegative integer labels $$L$$ such that

1. If $$(u, v) \in G$$ then $$L(v) - L(u) \in R(u, v)$$
2. The sum of $$L(v) - L(u)$$ for all $$(u, v) \in G$$ is minimized

Are there any similar problems that can read about to give me some insight?

• The obvious linear program may [a priori] return fractional solutions, if you round every $L(u)$ up to the nearest integer, or instead round every value of $L(u)$ down, I think that this will return a solution satisfying 1 and will change the value of the quantity as in 2. by no more than an additive $|E(G)|$. BUT, I don't know how good of an approximation ratio this is; the challenge is in instances where the sum $\sum_{uv \in E(G)} \min R(u,v)$ is small relative to $|E(G)|$; especially in instances where there are a lot of edges $uv$ such that $0 \in R(u,v)$. – Mike Apr 18 at 22:35