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 prob-lem in a Flow Network. (10 pt)
(c) Using the solution to the resulting Max Flow problem explain whether there is a Fea-sible Circulation in G. (5 pt)
1
Problem 2
Solve Kleinberg and Tardos, Chapter 7, Exercise 31. (25 pt)
2
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)
3
Problem 4
Due to large-scale flooding in a region, paramedics have identified a set of n injured people distributed across the region who need to be rushed to hospitals. There are k hospitals in the region, and each of the n people needs to be brought to a hospital that is within a half-hour’s drive to their current location. (So different patients will be able to be served by different hospitals depending upon the patients’ locations.) However, overloading one hospital with too many patients at the same time is undesirable, so we would like to distribute the patients as evenly as possible across all the hospitals. So the paramedics (or a centralized service advising the paramedics) would like to work out whether they can choose a hospital for each of the injured people in such a way that each hospital receives at most (n/k + 1) patients. (25 pt)
(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 bal-anced 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)
4
Practice Problems
Problem 5
Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
5
