Welchen Optimierungsalgorithmus brauch ich

[BUG]

Zitat von Gutelo:

Es soll nicht so laufen, dass alle Schuldner das Geld in einen Pott werfen und anschliessed Glaeubiger aus dem Topf bezahlt werden. Ich moechte eine optimnierte Liste, wer an wen direkt was bezahlen muss.

Aber diese Methode gibt schon ein relativ gutes Ergebnis, von dem aus man lokal optimieren könnte.

OBdA gibt es niemanden mit t_i = 0, ansonsten lässt sich auch eine Lösung finden, in der diese Person keine Zahlungen empfängt oder sendet. Damit gibt auch eine untere Schranke für die Anzahl der Transaktionen: n/2. Entweder gibt es mehr Gewinner (t_i > 0) oder Verlierer (t_i < 0); diese Gruppe ist macht dann mindestens die Hälfte der Gesamtgruppe aus und jedes Mitglied muss mindesten eine Zahlung tätigen bzw. empfangen.

Damit hat man mit der Pott-Methode in jedem Fall weniger als doppelt so viele Überweisungen als das Optimum. Schonmal nicht schlecht.

Eine ähnliche Approximationsgüte erreichst du, indem du jedem Gewinner eine Kette von Verlierern anhängst, die denn Restbetrag jeweils an den nächsten Überweisen, bis es für keinen weiteren mehr reicht. Diese Ketten hängst du dann aneinander, bis die Reste wieder für einen Verlierer reichen. Alternativ könntest du jeden Gewinner an mehrere Verlierer überweisen lassen, wobei nur einer den Restbetrag zusätzlich erhält, den er dann an den nächten Gewinner überweist.

Insgesamt glaube ich nicht, dass dieses Problem im Allgemeinen besonders einfach zu lösen ist und in den real auftretenden Fällen beim Lotto das Optimum sehr stark von n-1 abweicht; eine Approximation wäre also nicht schlecht.

Zitat von Gutelo:

Falsche Denkweise. Die Gemeinschaft kauft 500 Lose. 4 Legen das Geld fuer 4 Lose aus, einer fuer 496 Lose. Ich verstehe das Problem nicht.

Ah, die Gruppe einigt sich vorher auf die Anzahl der Lose. Das hättest du auch vorher sagen können