I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with L and R as the total set of people. A directed edge from l to r means l gave r some money with weight w which is the weight of the edge. Now I'm an auditing firm and want to make sure that the total amount given out by a person should be as close as possible to the amount received by him. I can limit each such transaction (implying I can reduce the weight of any edge in the graph). What is the best way to solve this approximately with the minimum restrictions required (in terms of actual amount)?

Ex. if

a -> 10 -> b
b -> 10 -> c
c -> 5  -> a

can be limited to

a -> 5 -> b
b -> 5 -> c
c -> 5 -> a

by reducing 10 units of transactions


You can write a linear program. For each edge you have a restriction variable. You want to minimize the sum of the restriction variables. For constraints you want to have the sums of the differences between outgoing edges and the incoming edges (minus their restriction variables) to be smaller than a threshold that you choose.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.