Wednesday, July 12, 2006

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.....

No comments: