xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

扫码添加客服微信

扫描添加客服微信

算法代写 - 算法

时间：2020-11-26

Question 1. (9 marks)
Suppose that P is an m × n matrix, whose entries are non-negative integer. Imagine a game in which Alice
chooses an integer in [m] = {1, . . . , m} and Bob chooses an integer in [n] = {1, . . . , n}. When Alice chooses
i and Bob chooses j, then Alice pays Pi,j dollars to Bob. Alice’s goal is to minimize how many dollars she
pays to Bob, and Bob’s goal is to maximize how many dollars he receives. We will allow Alice and Bob to
choose their integers randomly.
Part a. (4 marks)
Suppose that, in the above game, Alice first chooses a probability distribution D over [m], and tells D to
Bob. Based on knowing D, Bob chooses his integer j ∈ [n], so that he maximizies the expected value of the
payment he receives, assuming Alice chooses her integer according to the distribution D. Then the expected
value of Alice’s payment to Bob is:
valueA(D) = n
max
j=1
EI∼D[PI,j ], (1)
where EI∼D means that the expectation is with respect to taking I to be a random integer in [m] sampled
according to the probability distribution D. For example D could give probability 12
on I = 1 and probability
12
on I = 2, and then we have
valueA(D) = n
max
j=1
P1,j
2 + P2,j
2 .
Show how to use a linear program to compute a probability distribution D for Alice that minimizes valueA(D)
as defined in (1). The linear program should have as variables the probabilities assigned by D to any integer
in [m], and should also have a variable for valueA(D). Prove that the optimal solution to your linear program
gives an optimal D and its value.
Part b. (5 marks)
Suppose next that, instead, Bob goes first and chooses a probability distribution F over [n], and tells F to
Alice. Based on knowing F, Alice chooses her integer i ∈ [n], so that she minimizes the expected value of
the payment she gives to Bob, assuming Bob chooses his integer according to the distribution F. Then the
expected value of Alice’s payment is:
valueB(F) =
m
min
i=1
EJ∼F [Pi,J ], (2)
where EJ∼D means that the expectation is with respect to taking J to be a random integer in [n] sampled
according to the probability distribution F. Using the strong duality theorem, prove that the maximum of
valueB(F) defined in (2) over all probability distributions F on [n] equals the minimum of valueA(D) defined
in (1) over all probability distributions D on [m].
Question 2. (15 marks)
Let G = (A ∪ B, E) be a connected undirected bipartite graph, where A and B are the two sides of the
bipartition. Consider the following system of linear constraints:
∀u ∈ A ∪ B : Xv:(u,v)∈E xuv = 1 (3)
∀e ∈ E : xe ≥ 0 (4)
Let x be a feasible solution to (3)–(4). Your goal in this question is to design a polynomial time algorithm
that, on input G and x, computes a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe.
Part a. (4 marks)
Let F = {e ∈ E : 0 < xe < 1} be the set of edges corresponding to the fractional coordinates of x. Prove
that, if F is not empty, the subgraph H = (V, F) of G has a cycle C. 2
Part b. (6 marks)
Assume that not all coordinates in x are integers. Use the cycle C to compute two feasible solutions x0 and
x
00 of (3)–(4), so that both x0 and x
00 have strictly fewer fractional (i.e., not equal to 0 or 1) coordinates
than x. Moreover, there should be a value p ∈ [0, 1] such that
x = px0 + (1 p)x
00
.
Hint: use the fact that C must have even length, and consider alternatingly adding and subtracting a value
to the xe variables for e ∈ C (i.e., you add a value for one edge, and subtract for the next edge in the cycle.)
Part c. (5 marks)
Use the previous subquestions and describe a polynomial time algorithm that, on input G and x, computes
a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe. Justify the correctness and running
time of your algorithm.