Dynamic Programming and Network Flow Problems

Posted on May 4, 2024 in Computers

True/False

F In a 0-1 knapsack problem, a solution that uses up all of the capacity of the knapsack

will always be optimal.

F Suppose that a new max-flow algorithm operating on a flow network G with integer

capacities finds a non-integer max-flow f, i.e., the flow assigned to each edge is not

necessarily an integer. Then there may exist some s-t cut (A,B) in G where

f out(A) – f in(A) is non-integer.

Explanation: value of max flow in a flow network will always be an integer and

the sum of flow going through each cut is always equal to the value of flow

T For every min-cut (A,B) and max-flow f in a flow network G, if e=(u,v) is a directed

edge with u ε A and v ε B, then f(e) = ce.

●Explanation: By the Max-Flow Min-Cut Theorem, if (A,B) is a min-cut and f is a

max-flow, then v(f) = c(A,B). However, if f(e)

u in A and v in B, then v(f) ≤ Σe out of A f(e) e out of A ce = c(A,B), a contradiction.

F When the Ford-Fulkerson algorithm terminates, there must not be any directed edge

going out of the source node S in the residual graph.

● Explanation: This only happens if a min cut is right next to S but this may not

be the case.

T If removing an internal node u from a flow network G disconnects its source from its

sink, then the number of iterations required for Ford-Fulkerson to find max-flow in G

will be bounded by the sum of the capacities of the edges going into u.

F In a flow network, if all s-t cuts have integer capacities then all edge capacities must

be integers.

F If all edge capacities in a flow network are the same constant integer, then a

maximum flow can be found in linear time using the Ford-Fulkerson algorithm.

● Explanation: Ford Fulkerson will still take O(mn)

gQ6svlbaFQCFQCBQChUAhUAgUAoVAIVAIbFUEagHAVm3ZsqsQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUJgWyHwf7eVtWVsIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCGwRRGoBQBbtGHLrEKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoHthUAtANhe7V3WFgKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCGxRBGoBwBZt2DKrECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCYHshUAsAtld7l7WFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQCWxSBWgCwRRu2zCoECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBDYXgjUAoDt1d5lbSFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChcAWRaAWAGzRhi2zCoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBAqBQqAQKAQKgUKgECgECoFCoBAoBLYXArUAYHu1d1lbCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhUAgUAoVAIVAIFAKFQCFQCBQChUAhsEUR+P9Txax2dFQi+wAAAABJRU5ErkJggg==

wVXlfvw1ufAAAAABJRU5ErkJggg==

Dynamic Programming Problem 1 (20 pts)

Tommy has just joined the boy scouts and he’s eager to earn some badges. He’s got summer holidays coming up which will last for N days. Each day, he can earn points by doing any one activity among hiking, swimming, or camping. The camp instructor has posted the amount of points each activity can earn you on each day. For example, on the ith day, camping is worth c[i] points, hiking h[i] points and swimming s[i] points. However, Tommy gets bored doing the same activity really easily. He cannot do the same activity two or more days in a row. Based on this information, devise a Dynamic Programming algorithm to maximize the number of points Tommy can earn. You may assume that all point values are positive, and remember he can only do one activity per day.

a) Define (in plain English) subproblems to be solved. (4 pts)

𝑂𝑃𝑇 𝑖,𝑗 = the maximum number of points Tommy can earn from the start until the ith day, given he does activity j on the ith day. -2 points if it is mentioned: “points earned ON the ith day” instead of until the ith day. -4 points for incorrectly defined subproblems

OR 𝑂𝑃𝑇 𝑖,𝑗 = the maximum number of points Tommy can earn from the ith day, until the end given he does activity j on the ith day.

b) Write a recurrence relation for the subproblems (6 pts) 𝑂𝑃𝑇𝑖,𝑗 = 𝑚𝑎𝑥(𝑂𝑃𝑇𝑖−1, 𝑘 + 𝑎𝑐𝑡[𝑗][𝑖] 𝑤ℎ𝑒𝑟𝑒 𝑗 ≠ 𝑘, 𝑗, 𝑘 ∈ {𝑐, ℎ, 𝑠}, 𝑎𝑐𝑡 = {𝑐, ℎ, 𝑠}) In the second variant, i-1 is replaced by i+1 in each of the terms on the RHS

c) Using the recurrence formula in part b, write pseudocode using iteration to compute the maximum number of points Tommy can earn. (5 pts) Make sure you specify

– base cases and their values(2 pts)

– where the final answer can be found (e.g. opt(n), or opt(0,n), etc.) (1 pt)

-2 points for not specifying base cases/values, or for incorrect base cases/values

-1 point for each mistake in pseudocode

-1 point for incorrect return value or incorrect final answer

d) What is the complexity of your solution? (1 pt)

Is this an efficient solution? (1 pt)

𝑂(𝑁)

Yes.

0 points for saying it is not efficient.


2) Consider LAX, a notoriously busy airport with many arriving passengers who want to get to their destinations as soon as possible. There is an available fleet of n Uber drivers to accommodate all passengers. However, there is a traffic regulation at the airport that limits the total number of Uber drivers at any given hour-long interval to 0 simultaneous drivers. Assume that there are p time intervals. Each driver provides a subset of the time intervals he or she can work at the airport, with the minimum requirement of aj hour(s) per day and the maximum bj hour(s) per day. Lastly, the total number of Uber drivers available per day must be at least m to maintain a minimum customer satisfaction and loyalty. Design an algorithm to determine if there is a valid way to schedule the Uber drivers with respect to these constraints. (20 pts)
CBh59g+utldDwBAwBAwBQ8AQMAQMgQhEwMhzBA6qnZIhYAgYAoaAIWAIGAKGgH8Q+H8vUnkeou5FCQAAAABJRU5ErkJggg==

Solution: We will reduce the Uber driver’s problem to a circulation problem. First, we build a bipartite graph having the drivers Ubi on one side and hour-long time intervals Ij on the other side. We insert the edge between driver Ubi and time interval Ij if the driver prefers to work at that hour. The capacity of this edge is 1. There could be many drivers willing to work at that hour, so having flow 0 on that edge is interpreted as a driver not covering that time interval. Next, we add two new vertices x and y. Connect x to all Ubi and all Ij to y. The edge (x, Ubi) has lower bound ai and upper bound bi. The edge (Ij, y) has capacity k. Finally, we add the edge (y, x). The flow on this edge represents the total number of Uber drivers serving the airport. Claim. There is a valid way to schedule the Uber drivers if and only if there is a feasible circulation in H. 

Forward Claim: Assume that there is a valid way to schedule at least m Uber drivers per day. We construct a flow in H as follows. If a driver Ubiworks during a time interval Ij, we create a flow of one unit on edge (Ubi, Ij). A particular driver Ubi may work during several time intervals. Therefore, we set the flow along the edge (s, Ubi) to the number of time intervals that driver works. We set the flow along the edge (Ij, t) to the number of drivers who work during that time interval Ij. Finally, we set the flow on edge (t, s) to the total number of Uber drivers serving the airport. Thus, we have constructed a feasible circulation.

Backward Claim: Consider a feasible circulation in H. For each edge (Ubi, Ij) that carries one unit of flow, driver Ubiworks at hour Ij. Flow on the edge (s, Ubi) represents the total number hours that driver works. By the flow conservation law, that number is between ai and bi. Similarly, the flow along the edge (Ij, t) cannot exceed k, implying that only at most k drivers can work at that hour Ij.

Q5. USC has resumed in-person education after a one-year break, with k on-site courses available this term, labeled c1 through ck. Additionally, there are n students, labeled s1 to sn, attending these k courses. It’s possible for a student to attend multiple on-site courses, and each course will have a variety of students enrolled. (20 points)
(a) Each student sj wishes to enroll in a specific group pj of the k available courses, with the condition that each must enroll in at least m courses to qualify as a full-time student (where pj is greater than or equal to m). Furthermore, every course ci can only accommodate a maximum of qi students. The task for the school’s administration is to verify whether every student can register as a full-time student under these conditions. Propose an algorithm to assess this scenario. Prove your algorithm is correct by making an if-and-only-if claim.
(b) Assuming a viable solution is found for part (a) where each student is enrolled in exactly m courses, there arises a need for a student representative for each course from among the enrolled
students. However, any single student can represent at most r (where r is less than m) courses in which they are enrolled. Develop an algorithm to check whether it is possible to appoint such representatives, building on the solution from part (a) as a foundation. Prove your algorithm is correct by making an if-and-only-if claim.

Solution: Part (a)

We can solve the problem by constructing a network flow graph and then running Ford–Fulkerson algorithm to get the max flow. If the max flow is equal to nm, then all students can be enrolled as full time students. The setup of the graph is described below.
1. Place the n students and k classes as vertices in a bipartite style graph. Connect each student sj with all the classes in pj using edges with capacity of 1.
2. Place a sink vertex which is connected to all the classes (or alternatively students). Also, place a source vertex which is connected to all the students (or alternatively classes).
3. Connect all sj student vertices to the source (or sink) vertex with capacity of m.
4. Connect all ci class vertices to the sink (or source) vertex with capacity of qi
The enrollment is feasible if and only if there exists a max flow of nm.

Solution: Part (b)

We can solve the problem by starting from the solution from part (a). We will modify the constructed network flow graph slightly and then will run Ford–Fulkerson algorithm to get the max flow. If the max flow is equal to the number of classes k, then a selection exists otherwise no such selection exists. The setup of the graph is described below.
1. Use the same nodes as constructed in Part (a) of the solution.
2. The course selections (edges between students and courses) for each student will be reduced to what is available in the solution from part (a) (our feasible solution). i.e. we will remove some edges between students and courses that they did not get to sign up for.
3. The capacity of student to class edges will remain the same (i.e.1).
4. Assign 1 as the capacity from classes to sink (or alternatively source) vertex. (As there can only be 1 student representative from each class.)
5. Assign r capacity for edges between source (or alternatively sink) and student vertices. The selection is feasible if and only if there exists a max flow of k.
Rubric Part A (10 pts) 8 pts: Correct construction of the network flow graph. −2 pts: For each incorrect edge weight. 2 pts: Correct claim Rubric Part B (10 pts) 8 pts: Correct construction of the network flow graph. −2 pts: For each incorrect edge weight. 2 pts: Correct claim