Transactions Minimization Problem

In April 2000, I visited Agra with one of my friends (Amit) and his roommates (X,Y,Z) . At the end of the tour we ended up owing money to each other, due to the transactions during the trip (Eg : Amit paid for my taxi, I paid for X's food, Y paid for Amit's photo's at taj mahal etc etc.,). At the end of the trip we have to decide "who owes whom how much".

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,

1. Net amount (payed/received) is preserved for each person. (I am too lazy to write down the equations)
2. |E'| is as small as possible (or)
   
3. The sum of the weights of the edges in G' is minimized (or)
   
4. 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.....