Problem 1
In the network G below, the demand values are shown on vertices (supply value if negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. You need to show all your steps. (25 pt)
(a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds. (10 pt)
(b)Reduce the Feasible Circulation problem obtained in part a to a Maximum Flow problem in a Flow Network. (10 pt)
(c) Using the solution to the resulting Max Flow problem explain whether there is a Feasible Circulation in G. (5 pt)
Problem 2
Solve Kleinberg and Tardos, Chapter 7, Exercise 31. (25 pt)
Problem 3
At a dinner party, there are n families {a1,a2,...,an} and m tables {b1,b2,...,bm}. The ith family ai has gi members and the jth table bj has hj seats. Everyone is interested in making new friends and the dinner party planner wants to seat people such that no two members of the same family are seated in the same table. Design an algorithm that decides if there exists a seating assignment such that everyone is seated and no two members of the same family are seated at the same table. (25 pt)
Problem 4
(a) Describe a procedure that takes the given information about the patients’ locations(hence specifying which hospital each patient could go to) and determines whether a balanced allocation of patients is possible (i.e.each hospital receives at most (n/k+1) patients).
(11pt)
(b) Provide proof of correctness for your procedure. (10pt)
(c) What is the asymptotic running time of your procedure (in terms of n and k)?(4pt)
Practice Problems
Problem 5
Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
