### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 526 Class Note for CSE 565 at PSU

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Department

This 17 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 21 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 526 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 LECTURE 27 Network Flow 0 Application Bipartite Matching Adam Smith A Smith based on slides by S Raskhodnikova and K Wayne 10222008 1 Recently FordFulkerson K 0 Find maX st ow amp min st cut in 0mnC time All capacities are integers S C We will discuss how to remove this assumption 0 Duality Max ow value min cut capacity Integrality if capacities are integers then FF algorithm produces an integral maX ow 10222008 A Smith based on Slides by S Raskhodnikova and K Wayne Last time oiReduc ons Project Selection Problem Section 711 Reduction of proj ect selection to mincut Today Maximum bipartite matching Reducing MBM to max ow Hall s theorem 10222008 A Smith based on Slides by S Raskhodnikova and K Wayne MaTching MaTching InpuT undirecTed graph G V E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching Bipar ri re MaTching BiparTiTe maTching InpuT undirecTed biparTiTe graph G L U R E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching mafching 1239 3139 4539 Bipar ri re MaTching BiparTiTe maTching InpuT undirecTed biparTiTe graph G L U R E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching max mafching 1139 2239 3339 4439 ReducTions Roughly Problem A reduces To problem B if There is a simple algoriThm for A ThaT uses an algoriThm for problem B as a subrouTine Usually Given insTance x of problem A we find a insTance x39 of problem B Solve x39 Use The soluTion To build a soluTion To x Useful skill quickly idenTifying problems where exisTing soluTions may be applied Good programmers do This all The Time Reducing BiparTiTe MaTching To Maximum Flow Reduction To Max flow Cr39eaTe digraph G39 L U R U s T E39 Dir39ecT all edges from L To R and assign capaciTy 1 Add source s and capaciTy 1 edges from 3 To each node in L Add sink T and capaciTy 1 edges from each node in R To T Bipar ri re MaTching Proof of CorrecTness Theorem Max cardinaliTy maTching in G value of max flow in 639 Proof We need Two sTaTemenTs max maTching in G S max flow in G max maTching in G 2 max flow in G Bipar ri re MaTching Proof of CorrecTness Theorem Max car39dinaliTy maTching in G value of max flow in G39 Pf s Given max maTching M of car39dinaliTy k Consider flow 1 ThaT sends 1 uniT along each of k paThs f is a flow and has car39dinaliTy k Bipar ri re Matching Proof of Correc rness Theorem Max cardinali ry ma rching in G value of max flow in G39 Pf 2 LeT f be a max flow in G39 of value k In regrali ry Theorem gt k is in regral a capaci ries are 1 gt 1 is 01 Consider M se r of edges from L To R wi rh fe 1 each node in L and R par ricipa res in of mosT one edge in M IMI k consider cu r LU s R U T Exercises Give an example where The greedy algoriThm for MBM fails How bad can The greedy algoriThm be ie how far can The size of The maximum maTching global max be from The size of The greedy maTching local max WhaT do augmenTing paThs look like in This maxflow insTance Perfec r MaTching Def A maTching M Q E is perfecT if each node appears in exachy one edge in M Q When does a biparTiTe graph have a perfecT maTching STrucTure of biparTiTe graphs wiTh perfecT maTchings Clearly we musT have ILI IRI WhaT oTher condiTions are necessary WhaT conditions are sufficienT Per fec r MaTching NoTaTion LeT S be a subseT of nodes and IeT NS be The seT of nodes adjacent To nodes in S ObservaTion If a bipar39TiTe graph G L U R E has a per39feCT maTching Then IN 2 ISI for all subseTs S Q L Pf Each node in S has To be maTched To a differem node in NS No perfecf mafching S 2 4 5 N5 239 539 Marriage Theorem Marriage Theorem Frobenius 1917 Hall 1935 LeT G L U R E be a biparTiTe graph wiTh ILI IRI Then G has a perfecT maTching iff INS 2 ISI for all subseTs S Q L Pf gt This was The previous observaTion No perfecf maTching S 24 5 N5 239 539 Proof of Marriage Theorem Pf lt Suppose 6 does noT have a perfecT moTching For muloTe as a max flow problem wiTh oo consTr39oinTs on edges from L To R and let A B be min cuT in 639 By maxflow mincut copA B lt L I Choose 5 L D A copAB IL BIIR A Since min cuT con39T use 00 edges NS Q R D A IN5Is IR AI copABL B lt LL B ISI D 5 24 5 L B13 W RnA239539 Ns239539 Bipar ri re MaTching Running Time Which max flow algoriThm To use for biparTiTe maTching Generic augmenting paTh Om vaf Omn CapaciTy scaling Om2 log C Omz ShorTesT augmenTing paTh Om n1 2 NonbiparTiTe maTching STrucTure of nonbiparTiTe graphs is more complicaTed buT wellundersTood TuTTeBerge EdmondsGalai Blossom algoriThm On4 Edmonds 1965 BesT known Om n12 MicaIiVazirani 1980 Recently beTTer algoriThms for dense graphs eg On238 Harvey

### 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

#### "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!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.