Ford Fulkerson Algorithm: Irrational Capacities. The Ford-Fulkerson algorithm ma

Question

Ford Fulkerson Algorithm: Irrational Capacities. The Ford-Fulkerson algorithm may not terminate when arc capacities are allowed to be irrational. To see this consider the above maximum flow problem. Assume that all the arc capacities are infinite, except for the two bold arcs shown with capacities gamma and y^2. Here we set gamma - to be the golden ratio.1 Show that there is an infinite sequence of augmenting paths P_1, P_2, P_3,... such that the Ford-Fulkerson will never terminate if it augments along these paths in each iteration.

Explanation / Answer

Computers can’t represent anything but (small) integers or (dyadic) rationals exactly. Good question! One reason is that the integer restriction is literally artificial; it’s an artifact of actual computational hardware, not an inherent feature of the abstract mathematical problem. Another reason, which is probably more convincing to most practical computer scientists, is that the behavior of the algorithm with irrational inputs tells us something about its worst-case behavior in practice given floating-point capacities—terrible! Even with very reasonable capacities, a careless implementation of Ford-Fulkerson could enter an infinite loop simply because of round-off error!

See 15,2 in the link

http://www14.in.tum.de/lehre/2005WS/ea/16-maxflowalgs.pdf

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.