一站式論文代寫,英国、美国、澳洲留学生Essay代寫—FreePass代写

算法代寫 - 算法
時間: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.

在線客服

售前咨詢
售后咨詢
微信號
Essay_Cheery
微信
专业essay代写|留学生论文,作业,网课,考试|代做功課服務-PROESSAY HKG 专业留学Essay|Assignment代写|毕业论文代写-rushmyessay,绝对靠谱负责 代写essay,代写assignment,「立减5%」网课代修-Australiaway 代写essay,代写assignment,代写PAPER,留学生论文代写网 毕业论文代写,代写paper,北美CS代写-编程代码,代写金融-第一代写网 作业代写:CS代写|代写论文|统计,数学,物理代写-天天论文网 提供高质量的essay代写,Paper代写,留学作业代写-天才代写 全优代写 - 北美Essay代写,Report代写,留学生论文代写作业代写 北美顶级代写|加拿大美国论文作业代写服务-最靠谱价格低-CoursePass 论文代写等留学生作业代做服务,北美网课代修领导者AssignmentBack