Ratio-balanced maximum flows

DOI10.1016/J.IPL.2019.06.003zbMATH Open1461.05101arXiv1902.11047OpenAlexW2918008619MaRDI QIDQ2274503FDOQ2274503

Authors: Hannaneh Akrami, K. Mehlhorn, Tommy Odland 

Publication date: 20 September 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: 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 $iinS$ and at most $e_j$ units into node $jinA$. Then $s_j=e_j-su{m}_i{f}_{ij}$ is the unsecured part of account $j$. We are searching for the maximum flow that minimizes $su{m}_j{s}_j^2/e_j$.

Full work available at URL: https://arxiv.org/abs/1902.11047

Recommendations

• A POLYNOMIAL ALGORITHM FOR THE MAXIMUM BALANCED FLOW PROBLEM WITH A CONSTANT BALANCING RATE FUNCTION
• TWO EFFICIENT ALGORITHMS FOR THE GENERALIZED MAXIMUM BALANCED FLOW PROBLEM
• Balancing Applied to Maximum Network Flow Problems
• Maximum balanced flow in a network
• scientific article; zbMATH DE number 653269

zbMATH Keywords

financegraph algorithmspolynomial timemaximum flowsratio-balanced

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21) Special types of economic equilibria (91B52)

Cites Work

• Market equilibrium via a primal-dual algorithm for a convex program
• Improved balanced flow computation using parametric flow
• Efficient search for rationals

Cited In (1)

• Maximum balanced flow in a network

Uses Software

• CVXOPT

This page was built for publication: Ratio-balanced maximum flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274503)