Analysis of Algorithms
V. Adamchik CSCI 570 Lecture 9 University of Southern California
Network Flow – 2
Reading: chapter 7
The Ford-Fulkerson Algorithm
Algorithm. Given (G, s, t, c)
start with f(u,v)=0 and Gf = G.
while exists an augmenting s-t path in Gf
find a bottleneck
augment the flow along this path
update the residual graph Gf
16 B 12 C
13 14 4
FE
19 49
T
S10 7
Reduction
Formally, to reduce a problem Y to a problem X (we write Y ≤p X) we want a function f that maps Y to X such that:
• f is a polynomial time computable
• ∀instance y ∈ Yis solvable if and only if f(y) ∈ X is solvable.
Solving by reduction to NF
1. Describe how to construct a flow network
2. Make a claim. Something like “this problem has a feasible solution if and only if the max flow is …”
3. Prove the above claim in both directions
Discussion Problem 1
At a dinner party, there are n families a1, a2, …, an and m tables b1, b2, …, bm. The i-th family ai has gi members and the j-th 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 at 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. What would be a seating arrangement?
Discussion Problem 2
A company has n locations in city A and plans to move some of them (or all) to another city B. The i-th location costs ai per year if it is in the city A and bi per year if it is in the city B. The company also needs to pay an extra cost, cij > 0, per year for traveling between locations i and j. We assume that cij = cji. Design an efficient algorithm to decide which company locations in city A should be moved to city B in order to minimize the total annual cost.
Circulation
Given a directed graph in which in addition to having capacities c(u, v) ≥ 0 on each edge, we associate each vertex v with a supply/demand value d(v). We say that a vertex v is a demand if d(v) > 0 and a supply if d(v) < 0.
Necessary Condition
For every feasible circulation d(v) = 0 vV
Proof.
Reduction to Flow Problem
Circulation with Demands
There is a feasible circulation with demands d(v) in G if and only if the maximum s-t flow in G’ has value D.
d(v)=D d(v)0
Circulation with Demands and Lower Bounds
We are given a directed graph G=(V, E) with a capacity c(e) and a lower bound 0 ≤ l(e) ≤ c(e) on each edge and a demand d(v) on each vertex.
Circulation with Demands and Lower Bounds
L(v) = f0in(v) − f0out(v) d’(v) = d(v) - L(v).
[3,7] [5,7]
e
0
-5
b
12
[1,3] [2,5] d
c
[2,2]
-10 a
[5,10]
3
Circulation with Demands and Lower Bounds
-4
12
-5B 4
5
0
new G’
2
C
2
0
-10A F D -3 5 23
Claim: there is a feasible circulation in G iff there is a feasible circulation in a new graph G’.
Circulation with Demands and Lower Bounds
Summary: given G with lower bounds, we:
subtract lower bound l(e) from the capacity of each edge
subtract L(v) from the demand of each node solve the circulation problem on this new graph to
get a flow f.
add l(e) to every f(e) to get a flow for the original graph
Discussion Problem 4
Given the network below with the demand values on vertices and lower bounds on edge capacities, determine if there is a feasible circulation in this graph.
Discussion Problem 5
CSCI 570 is a large class with n TAs. Each week TAs must hold office hours in the TA office room. There is a set of k hour-long time intervals I1, I2, ... Ik in which the office room is available. The room can accommodate up to 3 TAs at any time. Each TA provides a subset of the time intervals he or she can hold office hours with the minimum requirement of
lj hour per week, and the maximum mj hours per week. Lastly, the total number of office hours held during the week must be H. Design an algorithm to determine if there is a valid way to schedule the TA's office hours with respect to these constraints.
Discussion Problem 6
The computer science department course structure is represented as a directed acyclic graph G = (V, E) where the vertices correspond to courses and a directed edge (u, v) exists if and only if the course u is a prerequisite of the course v. By taking a course w, you gain a benefit of pw which could be a positive or negative number. Note, to take a course, you have to take all its prerequisites. Design an efficient algorithm that picks a subset S⊂V of courses such that the total benefit is maximized.
benefit = ∑pw, where w∈S. goal: max benefit