Edmonds-Karp algorithm assignment

Assignment #6 CS4/531, Fall 2013 Due Date: Monday, Dec. 9, 2013, 3:00 - 4:00 pm. • UNSUPPORTED SOLUTIONS RECEIVE NO CREDIT. • Total points: 30 Note: The problems marked 0 points will not be collected nor graded. However, it is very important for you to do these problems as if they were to be graded. (Because similar problems will appear in exams). Detailed solutions to all problems (including 0 point problems) will be provided. • Guideline for all homework assignments – HW must be handed-in between 3:00 - 4:00pm Monday, Dec 9, during TA’s office hours. – Print your name, and UB number on the first page. – Staple all sheets together. Do not use notebooks and folders. – The solutions can be hand-written, but must be legible. – Present the solutions in sequential order. Make sure the problem number is clearly marked, and leave space between problems. – If you do not follow these guidelines, TA may deduct up to 20% of points. 1. (0 points) In the network shown in Figure 1, s1, s2, s3 are all sources. The supply available at s1 is sup(s1) = 5, at s2 is sup(s2) = 10, at s3 is sup(s3) = 5. The vertices t1, t2, t3 are all sinks. The demand required at t1 is dem(t1) = 5, at t2 is dem(t2) = 10, at t3 is dem(t3) = 5. The capacity of each edge is as indicated. Determine whether all the requirements can be met simultaneously. (Namely: the capacity constraint is satisfied for all edges; the flow conservation constraint is satisfied for the vertices a, b, c, d; the total flow out of each si (for i = 1, 2, 3) is sup(si); the total flow into each ti (for i = 1, 2, 3) is dem(ti).) To solve the problem, you need to convert it to an instance of the basic network flow problem, run the Edmonds-Karp algorithm, then answer the question. 1 2 3 1 7 4 s1 4 5 a 7 6 2 3 3 8 9 8 b c d 8 2 7 s2 s3 t1 t2 t3 Figure 1: The network for Problem 1 2. (8 points) Ad assignment problem. 1 Imagine that you work for Yahoo and are in charge of sending ads to users.