I have accounts with positive and negative balance and a pledge relationship between some. A pledge gives accounts with negative balance the right to retrieve money from the pledging account to cover their loss.
I want to find the optimal order of invoking this right of retrieving money.
1 2 3
A 1000 | -1000 -500 -500
B 1000 | -1000
In the given example account A and B have a positive balance of 1000 and accounts 1,2,3 are covered by priority (1 > 2 > 3). I want to cover as many accounts as possible by distributing the money of A and B on 1,2,3 while honoring the priority.
In this particular example choosing A1 as my first pair would result in only covering 1000 but if I choose B1, A2, A3 I have the optimal solution of covering 2000.
How is this kind of optimization problem called and what are the algorithms to tackle it?
It's basically a network flow problem. I'll draw the capacitated graph for your example (unlabeled arcs have infinite capacity). s is the source and t is the sink.
>A------->1
1000/ |\ ^\
/ | \ / \1000
/ | \ / \
/ | \ / 500 v
s | /->2--->t
\ \ / ^
\ \/ /
\ /\ /500
1000\ / \ /
>B --->3
The answer isn't the max flow; it's the flow that maximizes 1, then 2, then 3. One poly-time algorithm is to modify a max flow algorithm based on augmenting paths (simple paths!—otherwise we might take flow away from a higher priority account) preferentially to augment paths via 1, then 2, then 3.