CSCI 570  Homework 9

CSCI 570 
Homework 9
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.
4. Consider a case where there are n tasks, with time requirements r1, r2, ..., rn hours. On the project team, there are k
people with time availabilities a1, a2, ..., ak. For each task i and person j, you are told if person j has the skills to do task
i. You are to decide if the tasks can be split up among the people so that all tasks get done. People only execute tasks
they are qualified for, and no one exceeds his time availability. Remember that you can split up one task between multiple
qualified people. Now, in addition, there are group constraints. For instance, even if each of you and your two teammates
can in principle spend 4 hours on the project, you may have decided that between the three of you, you only want to
spend 10 hours. Formally, we assume that there are m sets Sj ⊆ {1, ..., k} of people, with set constraints tj . Then, any
valid solution must ensure, in addition to the previous constraints, that the combined work of all people in Sj does not
exceed tj , for all j. Note that one person may belong to at most one constraint set. Give an algorithm with running time
polynomial in n, m, k for this problem, under the assumption that all the Sj are disjoint, and prove that your algorithm is
correct.
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.
1 of 1 Professor: Dr. Shahriar Shamsian