Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Project SelectionBin Li10/29/2008Contents•Background•Problem Formulation•Algorithm DesignBackground•The telecommunication company is assessing the pros and cons of a project to offer some new type high-speed access service to residential customers.•The revenue from the high-speed access service might not be enough to updating the routers; however, once the company has updated the routers, they’ll earn more money.•These projects often interact each other. The question is: which projects should be pursued, and which should be passed up?Problem Formulation(1)•Problem–n projects 1,2,…,n–Dependencies between projects•Project i depends on project j implies project i cannot be done unless project j is done.–Each project i has a cost/profit pi•pi>0 implies project i generates pi profit•pi<0 implies project i requires a cost piProblem Formulation (2)•Constrains: For a set A of projects–A is a valid solution if A is dependency closed, that is for every , all projects that project i depends on are also in A.•Our goal–Find valid A to maximize profit(A)i A�( )ii Aprofit A p�=�Algorithm Design•Max-flow Min-cut theorem•If f is a flow in a flow network G=(V,E) with source s and sink t, then the following conditions are equivalent:–f is a maximum flow in G–The residual network Gf contains no augmenting paths.–|f|=c (S, T) for some cut (S, T) of G.Algorithm Design(2)•Build a flow network–Projects represented as nodes in a graph–If project i depends on project j, then (i, j) is an edge–Add source s and sink t–For each project i with pi>0, add edge (s, i) with capacity pi–For each project i with pi<0, add edge (i, t) with capacity –pi–For each dependency edge (i, j), we put capacity ∞ •We can see that the capacity of the cut({s},PU{t}) is , so the maximum-flow value in this flow network is at most C.: 0iii P pC p� >=�: 0iii P pC p� >=�Algorithm Design(3)•Example–There are four project{1,2,3,4},where p1>0,p2>0,p3<0,p4<0–project 1 is dependent on project 4–Project 2 is dependent on project 3Algorithm Design(4)•Lemma 1–Suppose (A’, B’) is a an s-t cut of finite capacity (no ∞) edges. Then projects in A=A’-{s} are a valid solution. •Proof–If A=A’-{s} is not a valid solution then there is a project and a project such that i depends on j.–Since (i, j) capacity is ∞, implies the cut(A’,B’) capacity is ∞, contradicting assumption.i A�j A�Algorithm Design(5)•Lemma 2–The capacity of the cut (A’,B’), where A’=AU{s} and A is a valid solution, is•Proof–Edge in the flow network:•The edges Leaving the source:•The edges Entering the sink:•Other edges: contribute Zero0 0i ii ii A and p i A and pp C p� > � >= -� �( ),ii Ac A B C p�� �= -�0iii A and pp� <-�( )0 0,i ii i ii A and p i A and p i Ac A B p C p C p� < � > �� �� �= - + - = -� �� �� � �Algorithm Design(6)Algorithm Design(7)•We have shown that if (A’,B’) is an s-t cut in G with finite capacity then –A=A’-{s} is a valid set of projects•Therefore a minimum s-t cut(A*,B*) gives a maximum set of projects A*-{s} since C is fixed.( ) ( ),ii Ac A B C p C profit A�� �= - = -�Thank you for your