Geek Answers Handbook

Balancing algorithm for equalizing differences?

Let's say we have N number of accounts with positive balances B_1, ..., B_n .

We can make a transfer T(from,to,amount) , which moves a certain amount of balance between accounts.

We have knowledge about the optimal distribution of residues O_1, ..., O_n .

The question arises: how can we find a minimal set of gears that achieve optimal distribution? Can we always avoid passing N-1 no more?

Example:

 Balances {0}: 10, {1}: 40, {2}: 50 Optimal {0}: 20, {1}: 60, {2}: 20 T(2,0,10) => {0}: 20, {1}: 40, {2}: 40 T(2,1,20) => {0}: 20, {1}: 60, {2}: 20
+8
algorithm
source share
1 answer

Yes, you can always avoid transmitting no more than N-1 . Here is the proof of induction:

  • For N=2 , it is obvious that no more than one transmission is required.
  • For N>2 there are two cases:
    • We are already in the optimal distribution, and in this case there is nothing to do.
    • There are i and j such that B_i > O_i and B_j < O_j . Transfer min(B_i - O_i, O_j - B_j) from account i to account j . This balances one of the two accounts, thereby reducing the problem to the case of N-1 .

The proof is constructive, giving you an algorithm. The algorithm does not try to minimize the number of transfers.

It is easy to come up with heuristics to reduce the number of steps. It’s a little late for me to think a lot about optimality, but it would not surprise me if the problem turned out to be NP-hard.

+5
source share

More articles:


All Articles