I'm confused. The article seems to require that people pay whoever they owe, as opposed to whoever is owed money. It seems we can simply sort the people by the amount owed, then have the person at the top of that list pay the person at the bottom, and repeat until all debt is resolved. This is an nlog(n) algorithm (for the sorting), and creates at most n edges (since, for every transaction, someone either pays back everything they owe, or someone gets paid everything they are owed).
> The article seems to require that people pay whoever they owe, as opposed to whoever is owed money. It seems we can simply sort the people by the amount owed, then have the person at the top of that list pay the person at the bottom, and repeat until all debt is resolved.
You could, but that's a solution to a different problem, not a different solution to the same problem. (Which is the right problem to solve is a social/customer/domain issue, rather than a technical one.)
How is it different? By the definition of equivalent in the article:
> when everyone in either graph pays the amounts they owe everyone else, they end up with the same amounts in the end.
It seems my algorithm also accomplishes that goal. I'm not sure that my algorithm is optimal, but I do think it's a good approximation and is somewhat simpler than the approximation in the article.
On review of the problem statement, it does appear that you are solving the problem they say they are solving, which appears to lack some of the constraints that seem to apply to the problem they are actually solving. (I suspect that the intent here was to show something about graph algorithms and so the problem statement is just insufficiently constrained, but its possible that the stated problem really is the interesting problem, and that the solution is unintentionally overconstrained because someone thought of a too-clever graph algorithm.)
6 comments
[ 3.1 ms ] story [ 11.3 ms ] threadIs there something I'm missing?
You could, but that's a solution to a different problem, not a different solution to the same problem. (Which is the right problem to solve is a social/customer/domain issue, rather than a technical one.)
> when everyone in either graph pays the amounts they owe everyone else, they end up with the same amounts in the end.
It seems my algorithm also accomplishes that goal. I'm not sure that my algorithm is optimal, but I do think it's a good approximation and is somewhat simpler than the approximation in the article.
On review of the problem statement, it does appear that you are solving the problem they say they are solving, which appears to lack some of the constraints that seem to apply to the problem they are actually solving. (I suspect that the intent here was to show something about graph algorithms and so the problem statement is just insufficiently constrained, but its possible that the stated problem really is the interesting problem, and that the solution is unintentionally overconstrained because someone thought of a too-clever graph algorithm.)
I don't see an explanation for this in the text - but a directed edge seems to switch from a semantic of "owes" to "is owed".