b) Find residual path that is "sufficiently" large.
Capacity scaling (Section 7.3)
O (m2 log U)
Find residual arcs with capacity > keep a network with
only those arcs.
Augment on paths
Update = / 2 until = 1
In each scaling phase ( value) there is a maximum of O(m) augmentations
[each augmentation O(m)] hence O(m2 log U)
2. Augment along shortest path 7.4
(smallest number of arcs)
Flavor of shortest path idea in preflow push discussion
Preflow Push Algorithms The best preflow push algorithms outperform the best path augmenting in theory and in practice.
Pushflow along individual arcs, not paths.
But, doing this may violate mass balance constraints.
A preflow is any flow satisfying
Flow bound constraints
2) for all
Flow entering can exceed flow leaving.
Thus, may violate mass balance constraint.
The idea is to push flow on arcs, violate mass balance, then restore mass balance (feasibility) for nodes.
Push toward the sink to do this, if we can't push toward the sink then push toward the source.
Definition e(i) excess of each node i N