Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Balancing algorithm to even out differences?

Tags:

algorithm

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 certain amount of balance between accounts.

We have knowledge about an optimal distribution of balances O_1, ..., O_n.

The question is: How can we find the minimum set of transfers that achieve the optimal distribution? Can we always get away with N-1 transfers at most?

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
like image 308
randomguy Avatar asked Sep 07 '14 19:09

randomguy


People also ask

Which load balancing algorithm is best?

Round-robin load balancing is the simplest and most commonly-used load balancing algorithm.

What are the common load balancing algorithms?

There are two primary approaches to load balancing. Dynamic load balancing uses algorithms that take into account the current state of each server and distribute traffic accordingly. Static load balancing distributes traffic without making these adjustments.

What is weighted least connection load balancing?

The weighted least connections algorithm maintains a weighted list of application servers with their number of active connections. The service forwards a new connection to a server based on the following combination: Its proportion to the weight or preference. Its number of active connections.


1 Answers

Yes, you can always get away with no more than N-1 transfer. Here is a proof by induction:

  1. For N=2, it is obvious that no more than a single transfer is required.
  2. For N>2, there are two cases:
    1. We are already at the optimal distribution, in which case there's nothing to do.
    2. There exist 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 N-1 case.

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

It is easy to come up with heuristics for reducing the number of steps. It is a bit late in the day for me to be thinking hard about optimality, but it would not surprise me if the problem turned out to be NP-hard.

like image 107
NPE Avatar answered Oct 11 '22 09:10

NPE