Let G = (V, E) be an undirected graph. For any subset A, BCV, let C(A,...

  

Transcribed Image Text:

Let G = (V, E) be an undirected graph. For any subset A, BCV, let C(A, B) denote the set of edges between A and B, i.e., C(A, B) = {e EE e connects some vertex in A and some vertex in B}. Note that, C(A, B) is also called the cut edges between A and B. In the cardinality maximum cut problem, the goal is to compute a partition of V into two sets S and S such that the cardinality of C(A, B) is maximized. . (10%) Consider the following randomized algorithm for max-cut. 1. For each v € V, pick x, € {0, 1} independently and uniformly at random. Let S = {v V: x₂ = 0} and S₁ := V - So. 2. Output (S0, S1). Prove that, for any e € E, Pr[e € C(S0, S₁)] = 1/2 and establish that C(S0, S₁) is a randomized (1/2)-approximation for the max-cut problem, i.e., the expected number of edges in C(S0, S₁) is at least one-half of the number in any optimal cut. Activate Windo Settings to Let G = (V, E) be an undirected graph. For any subset A, BCV, let C(A, B) denote the set of edges between A and B, i.e., C(A, B) = {e EE e connects some vertex in A and some vertex in B}. Note that, C(A, B) is also called the cut edges between A and B. In the cardinality maximum cut problem, the goal is to compute a partition of V into two sets S and S such that the cardinality of C(A, B) is maximized. . (10%) Consider the following randomized algorithm for max-cut. 1. For each v € V, pick x, € {0, 1} independently and uniformly at random. Let S = {v V: x₂ = 0} and S₁ := V - So. 2. Output (S0, S1). Prove that, for any e € E, Pr[e € C(S0, S₁)] = 1/2 and establish that C(S0, S₁) is a randomized (1/2)-approximation for the max-cut problem, i.e., the expected number of edges in C(S0, S₁) is at least one-half of the number in any optimal cut. Activate Windo Settings to

Answer rating: 100% (QA)

Step1 For any edge e E it connects two vertices u and v The probability that u and v ar... View the full answer