### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 223 Class Note for CSE 565 at PSU

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 39 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 17 views.

## Similar to Course at Penn State

## Reviews for 223 Class Note for CSE 565 at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Algorithm Design and Analysis a LECTURES 2224 I Counting Simple Paths Network Flow 0 Maximum FOW 0 Minimum Cut 0 F 0rdFulkerson A Smith A Smith based on slides by S Raskhodnikova and K Wayne 10152008 Review QuesTion How many simple paThs of lengTh k can Ther39e be in a graph wiTh n nodes Consider following code ModifiedDFSu isT paThsofar39 If u is in paThsofar39 r39eTur39n Else Add u To paThsofar39 If sizepaThsofar39ltk For all neighbors v of u ModifiedDFSvpaThsofar39 Does This run in Time 02k polyn Network Flow and Linear Programming 10152008 A Smith based on Slides by S Raskhodnikova and K Wayne Sovie r Rail Ne rwork 1955 5Wch Reference 0n fhe hisfory of fhe fransporfa on and maximum ow probems Alexander Schrijver in Ma rh Programming 91 3 2002 Maximum Flow and Minimum Cu r Max flow and min cuT Two very rich algor39i rhmic problems Cor39ner39sTone problems in combina ror39ial opTimizaTion Beau riful maThemaTical dualiTy NonTr39ivial applicaTions r educTions Data mining OpenpiT mining PPOJZC l SelecTion Air39line Scheduling Bipar TiTe maTching Image Segmentation ClusTer39ing NeTwor39k connecTiviTy NeTwor39k r eliabiliTy DisTr39ibuTed compuTing EgaliTar ian sTable maTching NeTwor39k inTr39usion deTeCTion MulTicamer39a Scene r39econsTr39ucTion Da ra pr39ivacy Many many more Minimum Cu r Problem Flow neTwork AbsTracTion for maTerial flowing Through The edges G V E direcTed graph no parallel edges Two distinguished nodes 3 source T sink ce capaciTy of edge e f 9 gt5f 10 4 15j source 5 5 k 8 f 15 4 6 capaci ry 39 4 3O 10 10 sink 15 10 V CuTs Def An 31 cm is a par TiTion A B of V wiTh s E A and T E B Def The capacity of a cuT A B is capAB 2 ce 2 out ofA 15 15 10 8 C6 10 D 4 6 15 10 Capaci ry 10 5 15 30 30 CuTs Def An 31 cm is a par TiTion A B of V wiTh s E A and T E B Def The capacity of a cuT A B is capAB 2 ce 2 out ofA g a Capaci ry 9 15 8 30 62 K 9 10 4 15 15 10 5 8 10 D s 3 A 4 6 15 10 4 i so Minimum Cu r Problem Min sT cuT problem Find an 31 cuT of minimum capaciTy 15 15 1o 1 A a i w L 6 15 10 J5 Capaci ry 10 8 10 30 7 28 Flows Def An sT flow is a funcTion 1 from E To real numbers ThaT saTisfies For39 each e E E 0 s fe s ce capaciTy For each v E V s T E e E e conservaTion emtov eoutofv Def The value of a flow 1 is Vf 2 fe eoutofs 0 9 4 O O 10 4 4 15 15 O 10 O 4 4 C9 5 8 C6 10 CD 0 o 4 o 6 15 o 10 capaci ry gt 15 flow gt O 0 GD 30 Value 4 Flows Def An sT flow is a funcTion 1 from E To real numbers ThaT saTisfies For39 each e E E 0 s fe s ce capaciTy For each v E V s T E e E e conservaTion emtov eoutofv Def The value of a flow 1 is Vf 2 fe e out of s 9 C5 10 10 4 4 15 15 O 10 C9 5 8 C63 10 CD 10 capaci ry gt 15 10 flow gt 11 11 GD 30 Value 24 Maximum Flow Problem Max flow problem Find sT flow of maximum value 9 9 10 1 9 10 4 O 15 15 0 1o 8 9 9 C9 4 10 4 o 6 15 o 10 capaCI ry gt 15 flow gt 14 14 Value 28 GD 30 Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 E e E e vf eoutofA eintoA 10 10 10 15 11 11 Value 24 30 Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 E e E e vf eoutofA eintoA 6 2 9 gt 10 O 6 10 4 4 15 15 O 10 3 8 8 s 5 3 8 10 D A 4 o 6 15 o 11 11 Value608111 4 30 24 Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 E e E e vf eoutofA eintoA 9 lt53 10 O 6 10 4 4 15 15 O 10 8 8 s 5 3 8 gtCigt 10 A 4 o 6 15 o 10 11 11 Value1048O10 24 Flows and CuTs Flow value lemma LeT f be any flow and IeT A B be any 31 cm Then 2 fe E fe Vf eoutofA eintoA Proof Vf Ef e e outo s by flow conserva rional rer ms gt E E 2 excepTVSGP60 vEA eoutofv eintov 2 fe 2 t eoutofA eintoA QuesTion Two problems min cu r max flow How do They r39ela re Flows and CuTs Weak duaIiTy LeT f be any flow and eT A B be any sT cuT Then The value of The flow is aT mosT The capaciTy of The cuT Big OpTimizaTion Idea 1 Look for39 sTr39ucTur39al consTr39ainTs eg max flow 5 mincuT CuT capaciTy 30 2 Flow value 5 3O gt 10 15 15 1o 5 8 10 G 15 4 6 15 10 C 39T 30 Q9 30 apaCI y Flows and CuTs Weak dualiTy L61 1 be any flow Then vf s capA B for any 31 cm A B Pf vf 2fe 2fe eoutofA eintoA S E fe e out ofA s 2 Ce e out ofA capA B Cer rifica re of Op rimali ry Corollary LeT f be any flow and la A B be any 31 cm If vf capA B Then 1 is a max flow and A B is a min 31 cm Value of flow 28 Cut capaci ry 28 2 Flow value 5 28 9 lt5 10 1 9 10 4 O 15 15 O 10 8 9 15 14 14 4 30 7 Towards a Max Flow Algor i rhm Greedy algor39iThm STar39T wiTh fe O for all edge e E E Find an 31 paTh P where each edge has fe lt Ce Augmem flow along paTh P RepeaT unTil you geT sTuck 1 0 39O o 20 1o 30 0 1o 20 Flow value O Towards a Max Flow Algor i rhm Greedy algor39iThm STar39T wiTh fe O for all edge e E E Find an 31 paTh P where each edge has fe lt Ce Augmem flow along paTh P RepeaT unTil you geT sTuck 1 20 EA 0 20 10 30 E20 10 20 0 lg 20 Flow value 20 Towards a Max Flow Algorithm Greedy algorithm Start with fe O for all edge e E E Find an st path P where each edge has fe lt Ce Augment flow along path P Repeat until you get stuck locally optimality 7b global optimality 1 1 20 2i 20 1o 20 1o 30 30 1o 20 1o 20 o la opt 30 gr39eedy 20 Residual Graph Original edge e u v E E COPGCW Flow fe capacity ce 17 6 flow Residual edge quotUndoquot flow sent e u v and eR v u Residual capacity Q 11 j 6 if EE cf f e if R E E residual capacity residual capacity Residual graph 6f 2 V E Residual edges with positive residual capacity Ef e 1 fe lt ce U eR ce gt O FordFulker39son Algor i rhm O N 000 0 v FordFulker39son Algor i rhm We gt 60 10 L O 7amp1 10 flow capaci ry 1 Flow value O FordFulker39son Algor i rhm 2 4 flow ca aci r P Y 8 12 8 0 1o 2 O 6 O 10 O L L 8 K s 10 3 5 Flow value O V 10 39 T 2 4 r39esidual capaci ry 1o 2 8 6 10 00E 0 OO FordFulker39son Algor i rhm 1o 2 6 O 10 2 0 i 9 N 10 X s 10 9 9 15 1o Flow value 8 FordFulker39son Algor i rhm Flow value 10 FordFulker39son Algor i rhm 2 4 G 10 K 8 O X 8 8 10 s 10 3 9 15 10 t Flow value 16 4 Gf 6 10 2 86L 4 6 8 2 coco Ab FordFulker39son Algor i rhm X 3 2 4 4 61 10 x 7 X 9 10 2 0 8 6 6 10 x 9 i isN 10 5 10 K 9 1o Flow value 18 2 2 Gf 8 1o 2 8 6 2 2 1 10 FordFulker39son Algor i rhm V 10 T Flow value 19 FordFulker39son Algor i rhm 39V U 10 CUT capaci ry 19 Flow value 19 2 Gf 10 2 s 1 3 r AugmenTing PaTh AlgoriThm Augmentf c P b lt bottleneck P Min residual capaci ry of an edge in P foreach e E P if e E E f e lt f e b forward edge else f e lt f e b reverse edge return f Ford FulkersonG s t c foreach e E E fe 0 Gf residual graph while there is an s t path P in G f t Augmentf c P update Gf return f FordFulkerson Summary so far FordFulkerson While you can Greedin push flow UpdaTe residual graph Lemma 1 This oquuTs a valid flow Proof Check conservaTion condTions see book STiII To do Running Time in parTicular TerminaTion How good a flow Running Time AssumpTion All capaciTies are inTegers beTween 1 and C InvarianT Every flow value fe and every residual capaciTy cf e remains an inTeger ThroughouT The algoriThm Theorem The algoriThm TerminaTes in aT mosT vf s nC iTeraTions Pf Each augmenTaTion increase value by aT leasT 1 Running Time of FordFulkerson OmnC Space Omn Corollary If C 1 FordFulkerson runs in Omn Time MaxFlow MinCUT Theorem AugmenTing paTh Theorem Flow 1 is a max flow iff There are no augmenTing paThs Maxflow mincuT Theorem EliasFeinsTeinShannon 1956 FordFulkerson 1956 The value of The max flow is equal To The value of The min sT cuT Pf We prove boTh simulTaneously by showing i iii are equivalenT i There exisTs an sT cuT A B such ThaT vf capA B ii Flow 1 is a max flow and AB is min sT cuT iii There is no augmenTing paTh relaTive To 1 i 2 ii This was The corollary To weak dualiTy lemma ii 2 iii We show conTraposiTive LeT f be a flow If There exisTs an augmenTing paTh Then we can improve 1 by sending flow along paTh Proof of MaxFlow MinCUT Theorem iii gt i LeT f be a flow wiTh no augmenTing paThs LeT A be seT of verTices reachable from s in residual graph By definiTion of A s E A By definiTion of f T 6E A ObservaTion No edges of The residual graph go from A To B original neTwork Claim 1 If e goes from A To B Then fe ce Proof OTherwise There would be residual capaciTy and The residual graph would have an edge A To B Claim 2 If e goes from B To A E fe E e The eoutofA eintoA Proof OTherwise residual edge E ce e out ofA would go from A To B capAB Running Time AssumpTion All capaciTies are inTegers beTween 1 and C InvarianT Every flow value fe and every residual capaciTy cf e remains an inTeger ThroughouT The algoriThm Theorem The algoriThm TerminaTes in aT mosT vf s nC iTeraTions Pf Each augmenTaTion increase value by aT leasT 1 There are aT mosT nC uniTs of capaciTy leaving source s Running Time of FordFulkerson OmnC Space Omn Corollary If C 1 FordFulkerson runs in Omn Time InTegraliTy Theorem If all capaciTies are inTegers Then There exisTs a max flow 1 for which every flow value fe is an inTeger Pf Since algoriThm TerminaTes Theorem follows from invarianT

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.