Final Examination CS 538
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Final Examination CS 538
Date: May 3rd, 2023 5-7 pm
Do problems 1-3 in class and 4-6 a home, due Thursday 4th May.
10 Bonus points included in take home part
1. (a) Suppose a flow network has losses on each edge such that the the flow on edge e is multiplied by a factor le as it travels across the edge. Write a linear program formulation of this problem. Find the dual of this LP. (15)
(b) State the KKT conditions for optimality in this setting. (5)
2. A bus company has n morning runs and n afternoon runs that it needs to assign to its n drivers. The runs are of different duration. If the total duration of the morning and afternoon runs assigned to a driver is more than a specified number D, the driver receives a premium payment for each hour of overtime. The company would like to assign the runs to the drivers to minimize the total number of overtime hours.
Formulate this problem as a matching problem and express its corresponding linear program. (15)
3. We define a most vital arc of a network as an arc whose deletion causes the largest decrease in the maximum flow value. Either prove the following claims or show through counterexample that they are false.
(a) A most vital arc is an arc with the maximum value of cij , where cij is the capacity of the edge (i,j).
(b) A most vital arc is an arc with the maximum value of fij , where fij is the flow through edge (i,j). (c) A most vital arc is an arc with the maximum value of fij among arcs belonging to some minimum cut. (15)
4. (A) Suppose that all capacities in a flow network are equal to a constant c. Professor Fluider suggests using the simplest augmenting path algorithm that iteratively finds augmenting paths in residual networks. What is the complexity of the algorithm?
(B) Let’s discover a way to improve the maximum flow algorithm that use blocking flows on layered networks.
(i) Derive upper and lower bound on the value of the minimum cut, if it exists.
(ii) Suppose the flow left to be pushed is f . Show that the length of the layered network is at most 2V/ ^(f/c) by answering the questions in the following proof idea:
There should be at least f/c edges across every pair of adjacent layers in the blocking network. Why? Let Vl be the number of vertices in layer l . Thus Vl −1Vl ≥ f/c. Why?
Then at least one of Vl −1 or Vl must be greater than or equal to ^f/c. Why?
Thus the length of the blocking network must be less than or equal 2V/ ^f/c
. Why?
(iii) So use blocking flow algorithm for at most S = 2V2/3 layered network steps. At this stage let g be the units of flow pushed. If f∗ is the maximum flow then the length of the network is ≤ 2V/ ^(f∗ − g)/c. Let f ∗ − g = cV2/3 . Then the length of the network is ≤ 2V2/3 Why?
After this use a straight forward push algorithm, pushing at all the flow in incremental pushes with at least one unit of flow in O(E) steps.
Analyze the complexity of the algorithm.
(20)
5. For the LP
Minimize z(x) = cT x
subject to Ax = b
x ≥ 0
where A ∈ Rm ×n ,x ∈ Rn , prove or disprove:
(a) If x1 and x2 are two BFS’s such that the total number of variables which are positive (in both together, i.e. in one or the other or in both) is at most m + 1 then x1 and x2 must be adjacent on the polytope. [10pts]
(b) No feasible solution in which m + 2 or more variables are positive can lie on an edge of the polyhedron.
[10pts]
6. (a) Prove that every path from the source to the sink in a directed graph contains at least one arc going from A to V − A from a s − t cut-set (A,V − A) [10pts]
(b) Determine an algorithm to find if the given directed graph contain k edge-disjoint paths from source to sink. [10pts]
2023-05-10