贪婪交易最小化算法的最优性

Question

最近我一直在阅读 Splitwise 问题，其中有一群人彼此之间存在债务，目标是用最少的交易数来解决这些债务。它也可以被建模为一个有向加权图，其中的边将被减少。

我遇到最多的解决方案是greedy iterative algorithm，首先计算每个人的净收益（欠他的钱-他欠的钱），然后重复以下内容：

1. take max. debtor X and max. creditor Y
2. if X owes more than Y is owed
     then X pays Y Y's value
          reduce X's debt by Y's value
          set Y's value to 0
     else X pays Y X's value
          reduce Y's value by X's debt
          set X's debt to 0

...直到每个人的价值都为0。

我的问题：

该算法在其产生的交易量方面真的是最优的吗？如果是，如何证明？
如果不是，该算法最优性的反例是什么，即可以用比其输出的交易更少的交易来最小化债务的情况？

Answer 1

看起来这个算法不是最优的。考虑 [-3, -2, -2, 3, 4] 的情况，其中正数表示债权人，负数表示债务人。使用所描述的算法，我们需要四次交易操作来消除所有债务：

>> [-3, -2, -2, 3, 4]
>> [0, -2, -2, 3, 1]    ([0] pays [4])
>> [0, 0, -2, 1, 1]     ([1] pays [3])
>> [0, 0, -1, 1, 0]     ([2] pays [4])
>> [0, 0, 0, 0, 0]      ([2] pays [3])

但是你可以看到，债务可以通过三笔交易清偿：欠3美元的人付给贷方3美元，然后欠2美元的人每人付给欠人4美元。

实际上，我认为所描述的算法的目标是最小化交易的总金额，而不是交易的数量，它确实做到了并且可以证明（尽管我不会在这里尝试） .

贪婪交易最小化算法的最优性

Optimality of greedy transaction minimisation algorithm

algorithm

optimization

minimize