Normal human-beings might solve this problem in a step by step fashion through multiple transactions. Since we are computer sceintists, we will add some "constraints" and solve this problem "efficiently"'.

Formally speaking, we have a weighted directed graph G(V,E) where the vertices represent the people and a directed edge (u,v) with weight w means that u owes w-dollars to v.

For example, the following graph shows that a owes $10 to b, and b owes $20 to c.

There are two ways to perform the transactions.

First way :

- a withdraws $10 from ATM
- b withdraws $20 from ATM
- a pays $10 to b
- b pays $20 to c

Second way : reduce G to G' as shown below :

- a withdraws $10 from ATM
- b withdraws only $10 from ATM
- a pays $10 to c
- b pays $10 to c

Second way is better in the following sense :

- b has withdrawn just as much money as required.
- there are smaller (less money involved) transactions.
- often there are lesser transactions (you can construct a complicated example to see this)
- The transactions are still parallelizable !! (i.e., all the payments can occur simultaneously).

Formally, we want to reduce the graph G(V,E) to G'(V',E') such that,

- Net amount (payed/received) is preserved for each person. (I am too lazy to write down the equations)
- |E'| is as small as possible (or)
- The sum of the weights of the edges in G' is minimized (or)
- The maximum weight of an edge in G' is minimized.

Question : Design an efficient algorithm to reduce G to G'

I will stop here and let you solve this problem on your own.....

## No comments:

Post a Comment