LAZY ALLOCATION ALGORITHM
Dinic’s algorithm is required for a general network. We hasten to add that
the matching problem we are required to solve has some additional proper-
ties. To recognize that, we organize the trades on the stock being sold in as-
cending order (group A) and the trades on the stock being bought in
descending order (Group B). Thus, each trade has a rank associated with it.
Also, if there is a feasible edge between the ith vertex in group A and the jth
vertex in group B, then there is a feasible edge between the ith vertex and all
the vertices in group B with rank greater than j. Similarly, there is a feasible
edge between the jth vertex in group B and all the vertices in group A with
rank less than i. This is illustrated in the ordering of the nodes in Figure 10.2.
To perform lazy allocation, we start from the vertex with the lowest
rank in group A and saturate the edge connecting it to the lowest possible
rank in group B. When the entire trade quantity from the vertex is accounted
for, we move on to the next vertex and do the same and work our way to the
last vertex. The consequence of the lazy allocation is that on a graph with
this structure, there is no flow augmenting path on the associated residual
graph, and the allocation is optimal. An example of such an allocation
method is demonstrated in Figure 10.2, configuration B.
Although there may not be any flow augmenting paths, there may be an
alternate flow routing on the residual graph, such that the flow along the di-
rected edge is zero. This implies that there could potentially be redundant
optimal routings.
170 RISK ARBITRAGE PAIRS