Maximum Flow and Minimum Cut Problems In this

Maximum Flow and Minimum Cut Problems In this

Maximum Flow and Minimum Cut Problems In this handout: Duality theory Upper bounds for maximum flow value Minimum Cut Problem Relationship between Maximum Flow and Minimum Cut Primal and Dual Problems in Optimization For many optimization problems, there is a dual problem associated with the primal (original) problem. The relationship between the primal and dual problems prove to be extremely useful in a variety of ways. Particularly, it helps to find efficient algorithms for solving the primal problem; provides arguments for proving the optimality (or close-tooptimality) of a primal solution. Next we will discuss the dual of Maximum Flow Problem, known as Minimum Cut Problem. Upper bounds for maximum flow value Recall our example. Can we give upper bounds on the maximum flow value before finding any augmenting paths? One possible upper bound is the total capacity of the arcs leaving the source: u Oi 4 5 4 13 arcs O i

Another upper bound is the total capacity of the arcs entering the sink: u jT 5 5 10 arcs j T Note that this upper bound is equal to the maximum flow value. Thus, we could recognize that the algorithm output is optimal simply by comparing the flow value with the upper bound. A 4 O 4 4 5 B 6 4 C 5 D 5 T Upper bounds for maximum flow value Consider another example given by the network below. C 4 A 2

8 T O 3 4 D 3 B 2 After solving the problem by the augmenting path algorithm (see blackboard), we get the following optimal residual network with maximum flow value equal to 5. 2 A 0 6 O 0 2 2 C 0 4 T

2 3 B 1 1 1 D 2 Upper bounds for maximum flow value Upper bounds for this problem: u Oi 8 3 11 u jT 4 3 7 arcs j T arcs O i Both of these upper bounds are strictly greater than the maximum flow value. Can we get a tighter (smaller) upper bound? Consider the set of directed arcs going from node set {O,A} to its complement node set {B,C,D,T}: Cut = {AC, OB}.

Any flow from node O to node T should go through the arcs of Cut. Thus, Maximum flow Capacity(Cut) = 2+3 = 5 . 5 is the best upper bound which is equal to the maximum flow value. A 2 C 4 8 O 3 T 4 B 2 D 3 Generalizing the Concept of Cut Let S be a subset of V such that OS and TS. Then the set of the arcs going from S to V-S is called a cut . S is called the O-side of the cut, and V-S is the T-side of the cut. E.g., Cut1={AC, BC, BD} with O-side={O,A,B} and T-side={C,D,T}. Cut2={OA, OB} with O-side={O} and T-side={A,B,C,D,T}.

In other words, a cut may be defined as a set of directed arcs such that if we remove the arcs of the cut, no directed path from the source to the sink will be left. C 4 A 2 8 T O 3 Cut2 4 B 2 D Cut1 3 Cut Capacities and Weak Duality Capacity of a cut is the total capacity of the arcs forming the cut. E.g., cap(Cut1) = 2+4+2 = 8, cap(Cut2) = 8+3 = 11. Note: The arcs going from T-side to O-side dont count in the cut. E.g., the cut defined by O-side={O,A,C} doesnt include arc BC :

Cut3 = {OB, CT} with cap(Cut3) = 3+4 = 7 . Weak duality property: Maximum flow value capacity of any cut , i.e., capacity of any cut is an upper bound on the maximum flow. E.g., cap(Cut3) = 7 > 5 = max flow value A 2 C 4 8 O 3 Cut2 T 4 B 2 Cut3 D Cut1 3 Proving the correctness of augmenting path algorithm Using the relationship between

flows and cuts, we prove below that the output of Augmenting Path Algorithm is really an optimal flow. Consider the optimal residual network of our example. Let S be the set of those nodes which are reachable from the source via augmenting paths: S={O, A}. Consider the cut that has S as its O-side: Cut = {AC, OB}. All the arcs of this cut are used up to capacity. Thus, the current flow = capacity of this cut. Hence the current flow is optimal (maximum). 2 A 0 6 O 0 2 2 C 0 4 T 2 3 B 1 1

1 D 2 Minimum Cut and Strong Duality The cut considered in the previous slide has the minimum possible capacity. Call it minimum cut. Summary of the procedure for finding minimum cut: Apply the Augmenting Path Algorithm to find an optimal residual network; Find the set S of the nodes which are reachable from O via augmenting paths; The cut that has S as O-side is a minimum cut. Based on the arguments of the previous slide, we have Strong Duality Property: Maximum flow value = Capacity of minimum cut 2 A 0 6 O 0 2 2 C 0

4 T 2 3 B 1 1 1 D 2 Minimum Cuts Why do we care about minimum cuts? Minimum cuts provide an intuitive argument for proving that our current flow is maximum. There are many applications where we need to find not a maximum flow but a minimum cut. Note that the maximum-flow-based procedure of the previous slide is the best way to find a minimum cut. The number of cuts in a network is exponential on the problem size; thus, finding a minimum cut by enumerating all the cuts is not efficient. Next time: Applications of Maximum Flow and Minimum Cut Problems

Recently Viewed Presentations

  • Azole resistance in Aspergillus  is it a problem?

    Azole resistance in Aspergillus is it a problem?

    Azole resistance in Aspergillus - is it a problem? Dr Susan J Howard The University of Manchester & Regional Mycology Laboratory Manchester * * * * * * * * * * * * * * * * * *...
  • Sources - C3 Teachers

    Sources - C3 Teachers

    Sources. THE INQUIRY DESIGN MODEL SESSION 3: These slides introduce the third component of the Inquiry Design Model™—sources. The Inquiry Design Model (IDM™) features sources as the primary means by which students encounter social studies content and practice the skills...
  • The Communication Passport - ENABLE Scotland

    The Communication Passport - ENABLE Scotland

    PABSS and Positive Behaviour Support. A new Scottish Charity promoting the use of Positive Behaviour Support (PBS) All behaviour happens for a reason and is a means of communication for people with learning disabilities.
  • Street art - Banksy

    Street art - Banksy

    pseudoniem 'Robert' of 'Robin Banks, waarschijnlijk Robin Gunningham. weinig zekerheid over de ware identiteit. 1973 geboren in Bristol. kunstwerken zijn vaak politiek en humoristisch van aard. Graffiti in combinatie met sjabloontechniek. verschillende Europese steden maar ook buiten Europa zoals in...
  • Chronic disease management The background Bob Lewin Professor

    Chronic disease management The background Bob Lewin Professor

    Chronic disease management The background Bob Lewin Professor of Rehabilitation Presentations at - www.yorkconference.org CARE AND EDUCATION RESEARCH GROUP
  • SCORM Sequencing and Navigation

    SCORM Sequencing and Navigation

    他們對ict 的用途與它的校外用途比較 訂定各階段ict發展指標 層級5 學生談論他們的使用ict 和它的校外用途、觀察的知識和經驗。他們估計對ict 的用途在他們的工作和能重要地反映追蹤工作的改進 層級6 學生使用基於ict 的模型做預測。
  • Lcls R & D

    Lcls R & D

    For security, server resides behind SLAC firewall and only viewable within the SLAC domain remote users can only view it if they have a SLAC account operating, for example, with VPN anyone at SLAC can in principal write to the...
  • Good To Great Chapter 3 - Texas Tech University

    Good To Great Chapter 3 - Texas Tech University

    Contrastingly other companies followed "genius with a thousand helpers" model . Genius cases. Primary driving force in company's success is the genius. Geniuses seldom build great mgmt teams because they don't need/want one. ... Good To Great Chapter 3