0
$\begingroup$

Me and my roommates don't split expenses right away but enter the amounts paid for others into a spreadsheet. So at the end of the month, we can pay each other the residual amounts. We discovered that many transactions can be avoided when "indirect payments" can be avoided (e.g. A has to give B 10€ and B has to give C 10€ then A can give the 10€ straight to C). This question told me that the maximum (and the usual) amount of these transactions is $n-1$. However, there is no description of how I can determine which transactions to do.

I want to automate the process of simplifying the transactions using scripts in the spreadsheet but I couldn't find any solution online (partly due to lack of knowing a word for this type of problem). I was thinking this may be some special form of transportation theory or something else to do with simplex, as I vaguely remember that being similar to what has to be achieved here (when you put the transactions into a matrix).

If anyone knows an algorithm to simplify the matrix for the transactions it would be highly appreciated.

$\endgroup$
  • $\begingroup$ "However, there is no description of how I can determine which transactions to do." Really? The first paragraph of the accepted answer seems to me to describe an algorithm. How does it break down? $\endgroup$ – Peter Taylor Apr 30 at 15:32
  • 1
    $\begingroup$ Well, my brain has deceived me, thanks for pointing that out. I failed to understand that answer as it starts out with the total debt of that person being paid and not what the second person owes. This stopped me from understanding the answer properly, as a solution... Since this Question is redundant then I'll delete it soon. Thanks for your help. $\endgroup$ – Emil S. Apr 30 at 15:52
  • $\begingroup$ Also see this question for more discussion. The problem is NP-complete. $\endgroup$ – Mike Earnest Apr 30 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.