User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse





Ratio-Balanced Maximum Flows


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)

(Preprint), 143KB

Supplementary Material (public)
There is no public supplementary material available

Akrami, H., Mehlhorn, K., & Odland, T. (2019). Ratio-Balanced Maximum Flows. Retrieved from http://arxiv.org/abs/1902.11047.

Cite as: http://hdl.handle.net/21.11116/0000-0003-B2FE-6
When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form of \emph{security}, which will be collected if the lender defaults. Accounts can be secured by several securities and a security can be used for several accounts. The goal is to fractionally assign the securities to the accounts so as to balance the risk. This situation can be modelled by a bipartite graph. We have a set $S$ of securities and a set $A$ of accounts. Each security has a \emph{value} $v_i$ and each account has an \emph{exposure} $e_j$. If a security $i$ can be used to secure an account $j$, we have an edge from $i$ to $j$. Let $f_{ij}$ be part of security $i$'s value used to secure account $j$. We are searching for a maximum flow that send at most $v_i$ units out of node $i \in S$ and at most $e_j$ units into node $j \in A$. Then $s_j = e_j - \sum_i f_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $\sum_j s_j^2/e_j$.