Assignment No 2- CS 538, S2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment No 2- CS 538, S2023
Date Due: Feb 19th, 2023
1. Design the dual of the following Linear Problem: max cT x
such that
ai(T)x ≤ bi , 1 ≤ i ≤ m\
aj(T)x = bj , m\ + 1 ≤ j ≤ m
xk ≥ 0, 1 ≤ k ≤ r
where x = (x1 ,x2 . . . xn ),x ∈ Rn
2. Show that all linear programs can be expressed as min cT x
Ax = b
x ≥ 0
where x = (x1 ,x2 . . . xn ),,x ∈ Rn .
3. We consider an attacker on your flow network. Consider a bipartite network N(E,d) where E = {e1 ,e2 , ··· ,em } . We denote your (the designer’s) budget by BD . The flow design is represented by a vector f ∈ [0, 1]m with the requirement 对 f[i] = 1, where f[i] is the flow amount on edge ei . For each edge ei with flow amount f[i], the designer’s cost is d[i]f[i]. We say a design f is within budget if 对 d[i]f[i] ≤ BD . An attack is a vector X ∈ [0, 1]m indicating the attack on edges, where X[i] denotes the attack, or attack level, on edge ei , the fraction of flow captured on ei .
The adversary’s benefit is the sum of flow she captures over the bipartition and defined as 对j(k)=1 f[j] · X[j]. Your goal is to minimize the attacker’s benefit.
Given the adversary’s strategy X[j] as fixed and provided, describe a linear program to optimize the designer’s strategy and find its dual.
4. Set up a linear program for determining a shortest path in a weighted directed graph. Find the dual of this LP.
5. Complete the proof from Class: Compute the dual of linear program for the maximum flow problem using path structures instead of flow conservation at vertices. Use variables for flows on s-t paths, where a path is the sequence of edges from s to t. Explain how this can be used to prove the strong duality of the maximum flow problem.
6. A system Ax ≤ b,x ∈ Rn ,A ∈ Rm ×n may be infeasible, i.e. has no solution. Show that this is true iff there exists a y ∈ Rm such that AT y = 0,bT y < 0, and y ≥ 0.
2023-03-14