4
$\begingroup$

Here's my precise situation: I have a graph with nodes $V$ and edges $E$, and the nodes have some non-negative integer weights $w_i$. In one step of the protocol, I am now allowed to move weight around among nodes. This is expressed through a flow $f$ defined on the edges: $f(i,j)$ tells me how much weight I transfer from $i$ to $j$.

  • The flow cannot create new weight.
  • The flow must be integer.
  • $f(i,j)$ is allowed to be larger than $w_i$, but after the entire flow has been applied all the $w_i$ must be non-negative again.

Let $\Delta_i$ be the total change in the weight on node $i$, with the sign convention such that $\Delta_i$ is positive if more tasks leave node $i$ than arrive at $i$. An upper bound on $\Delta_i$ is $w_i$, by virtue of the third condition on the flow. My question now is: Is there also a lower bound?

A naive lower bound for each $\Delta_i$ would be given by the sum of the $\Delta_j$ for all neighbors of $i$, but I wonder if some network- and graph-theory can find better bounds?

If a good lower bound on the $\Delta_i$ is not possible, maybe there is a good \emph{upper} bound on the quantity $$\sum_{i \in V} \Delta_i^2$$?

$\endgroup$
  • $\begingroup$ It looks interesting. Is there any motivation/application for this problem. $\endgroup$ – Arman Apr 2 '11 at 19:28
  • $\begingroup$ Yes, I'm studying a random protocol for load balancing: The weights are the number of (unit-size) tasks per node. Each tasks migrates to another node with a certain probability, leading to an expected flow. I want to compare the expected flow with the optimal flow. This is the flow that leads to the largest drop in the potential function $\sum_i w_i(w_i+1)/s_i$, where the $s_i$ are (integer) speeds of the node. $\endgroup$ – Lagerbaer Apr 2 '11 at 19:34
4
$\begingroup$

I think you're using a confusing sign convention, but I'll stick with it. It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm misunderstanding something), so the lower bound you'll get is $$\Delta_i\geq -\sum_{i\in V}w_i.$$

Things won't really be better for bounding the square. For example, if your graph is a star in which every leaf has $w_i=1$, then $$\sum_{i\in V}\Delta_i^2 = (|V|-1)+(|V|-1)^2.$$

You can't get a neighbourhood restriction, either, because you can take the example of a $k$-ary tree in which every leaf has weight 1 and all the weight goes to the root.

What you can get, however, is the possibly useful bound $$\sum_{i\in V}{|\Delta_i|} \leq 2\sum_{i\in V}w_i.$$

To see this, just note that when charge leaves a vertex you'll count it twice.

$\endgroup$
  • $\begingroup$ Thank you. Okay... I guess I then have to work out some bounds that take into account more properties of the specific flow I'll get. Since explaining these properties here would take too long, and the value for anyone but myself would be close to zero, I'll just leave it at that. $\endgroup$ – Lagerbaer Apr 3 '11 at 15:46

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.