Description

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.

(a) Reduce the Feasible Circulation with Lower Bounds problem to a Feasible Circulation problem without lower bounds.
(b) Reduce the Feasible Circulation problem obtained in part a to a Maximum Flow problem in a Flow Network.
(c) Using the solution to the resulting Max Flow problem explain whether there is a Feasible Circulation in G.
2. Determine if the following statements are true or false. Give reasoning for your answer.
(a) There is a feasible circulation with demands {dv} if Σvdv = 0.
(b) In a flow network, the value of flow from S to T can be higher than the maximum number of edge disjoint paths from S to T.
(c) There always exists a maximum flow without a cycle containing positive flow.
(d) If you have non integer edge capacities, then you cannot have an integer max flow.
3. Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
5. A company has n different teams. Each team i has ti members. In order to improve inter-team communication, the company has decided to organize m events. Each event j can have at most ej attendees. To encourage attendees to communicate with other teams, the company has decided that each event should not have more than two attendees from the same team. Also, there are certain events which need attendees from some specific teams. More specifically, there are k constraints of the form (a,b) which means that the company needs at least one attendee from team a for event b. The company wants every employee to attend an event. The company also wants every event to be full. Give an efficient solution to assign employees to events, such that all of the company’s requirements are fulfilled.
6. Solve Kleinberg and Tardos, Chapter 7, Exercise 31.