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?

  • 2
    $\begingroup$ 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)$. $\endgroup$ – Mike Apr 18 at 22:35

Thanks Mike, for some reason I hadn't thought to formulate it as a linear program. But once you do that, the answer is obvious. In fact, when you set up the linear program, the resulting matrix is totally unimodular. Which means it can be solved quite easily by any linear solver and the result will be an integer solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.