[SOLVED] CS AI algorithm Analysis of Algorithms

Analysis of Algorithms
V. Adamchik CSCI 570 Spring 2020 Lecture 10 University of Southern California
Network Flow 2
Reading: chapter 7

Exam Statistics
Number of submitted grades: 570 / 582 Minimum: 24 %
Maximum: 94 %
Average: 74.28 %
Median:76 %
Standard Deviation:9.75 %

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

Cuts and Cut Capacity
G 19
T
16 B 12 C 49
S10 7
13 14 4
FE
12
B
12
4
C
Gf
19
S 10 4 7 T
9 2
11 F 3 11
4
E

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 Y is 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 f1, f2, , fn and m
tables t1, t2, , tm. The i-th family fi has ri relatives and the j-th table tj has sj 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
There are n students in a class. We want to choose a subset of k students as a committee. There has to be m1 number of freshmen, m2 number of sophomores, m3 number of juniors, and m4 number of seniors in the committee. Each student is from one of k departments, where k = m1 +m2 +m3 +m4. Exactly one student from each department has to be chosen for the committee. We are given a list of students, their home departments, and their class (freshman, sophomore, junior, senior). Describe an efficient algorithm based on network flow techniques to select who should be on the committee such that the above constraints are all satisfied.

Discussion Problem 3
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.

Discussion Problem 4
The edge connectivity of an undirected graph G = (V, E) is the minimum number of edges whose removal disconnects the graph. Describe an algorithm to compute the edge connectivity of an undirected graph
a
bsd
h
gf
e

Circulation
Suppose that there can be a set S of sources generating flow, and a set T of sinks that can absorb flow. As before, there is an integer capacity on each edge.
We call this circulation since we have s-t flow as well as t-s flow.
Goal is to find a circulation.

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 ConditionFor every feasible circulation d(v) = 0 vVProof. Reduction to Flow Problem Circulation with DemandsThere 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 BoundsWe 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[3,7] [5,7]e0-5b12[1,3] [2,5] dc [2,2]-10 a[5,10]3 Circulation with Demands and Lower Bounds L(v) = f0in(v) f0out(v)0d(v) = d(v) – L(v).-412-5B 45 new G2C20 -10A F D -3 5 23Claim: there is a feasible circulation in G iff there is a feasible circulation in a new graph G. Circulation with Demands and Lower BoundsSummary: given G with lower bounds, we:subtract lower bound l(e) from the capacity of each edgesubtract L(v) from the demand of each node solve the circulation problem on this new graph toget a flow f.add l(e) to every f(e) to get a flow for the original graphDiscussion Problem 5Given 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 6CSCI 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 oflj 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.