Friday, July 28, 2006

Network flow : integer vs real values

Integer values are assumed in the analysis of most of the algorithms based on network flow. The reason for this is as follows.....

If the capacities on all the edges are integral then there always exists an integral flow.

If the capacities are rational numbers we can take the LCM and apply the same network flow algorithm (ford-fulkerson) by choosing augmenting paths arbitrarily.

If the capacities are real numbers, ford-fulkerson algorithm runs in polynomial time if augmenting paths are chosen via BFS. The algorithm might not terminate if the augmenting paths are chosen arbitrarily.

Assuming integer values makes the analysis much simpler, without worrying about how the augmenting paths are chosen. As said earlier, real-values can be handled efficiently using BFS.

A recent paper [1] analyzes the DFS approach of choosing augmenting paths.

[1] Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data Brian C Dean, Michel X. Goemans, Nicole Immorlica. To appear in the proceedings of the 14th annual European Symposium on Algorithms (ESA), 2006.

No comments: