Consider the Ford-Fulkerson algorithm as described in Section 3.2 (augmenting paths have as few arcs as possible). This exercise shows that the algorithm terminates and solves the max-flow problem in polynomial time, even when the problem data are irrational. Let x0 be the initial feasible flow vector; let xk, k = 1, 2,..., be the flow vector after the kth augmentation; and let Pk be the corresponding augmenting path. An arc (i, j) is said to be a k+-bottleneck if (i, j) is a forward arc of Pkand xk ij = cij , and it is said to be a k−-bottleneck if (i, j) is a backward arc of Pk and xk I= bij . (a) Sh
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here