这是一篇美国的算法代写
Instructions.
- Submit this homework only if your letter grade can change by improving your lowest score. We suggest you to look on Canvas and make sure your submission would have an impact on your grade.
- You can consult any material from class (suggested reading, videos, notes, etc). You cannot use external sources and you cannot collaborate with others.
- You can reference and use any result, theorem and design covered in class without proof.
- By taking this exam, you are agreeing to honor these instructions.
Problem 1
Konig’s Theorem establishes that on a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover.
(a) Show that this result does not hold in general, by given an explicit counterexample.
(b) Write the problem of finding the size of a maximum matching as an Integer Linear Programming. (Hint: consider a variable for each edge. Recalling the definition of a matching, you can write a constraint for each vertex.)
(c) Write the Dual ILP to your answer from part (b) and explain why the dual corresponds to Vertex Cover.
(d) Imagine solving the ILP from part (b) via randomized rounding. Show that the optimal solution to the relaxed LP gives an integer value solution, and hence rounding is not necessary. (Hint: think how would you go from the LP solution to an integer solution via rounding, then argue that there must have been an integral solution for the relaxed LP.)
(e) (Not for credit. Do not turn in.) Similarly, one can show the Vertex Cover LP problem has an integer value solution and conclude Konig’s Theorem via strong duality.
Problem 2
(Randomized algorithm for 2-SAT) Consider the following randomized algorithm to solve 2-SAT:
Randomized 2-SAT
- Start with an arbitrary truth assignment.
- Repeat up to M times, terminating if all clauses are satisfied:
(i) Choose an arbitrary clause that is not satisfied.
(ii) Choose uniformly at random one of the literals in the clause and switch the value of its variable.
- If a valid truth assignment has been found, return it.
- Otherwise, return that the formula is not satisfied.
In this problem, you will study the number of iterations of this algorithm. Assume the given formula do has
a valid assignment, S. Let Xt be the number of variables that have the same value as in S after t iterations.
Denote by n the number of variables of the boolean formula.
(a) If Xi = 0, what are the possible values of Xi+1? Briefly justify your answer.
(b) For 1 ≤ j ≤ n − 1, explain why
P(Xt+1 = j + 1 | Xt = j) ≥ 1/2
P(Xt+1 = j − 1 | Xt = j) ≤ 1/2.
(c) From (b), we conclude that the time it takes Xt to be equal to n is bounded by the time it takes Yt to get to n, where
P(Yt+1 = 1 | Yt = 0) = 1
P(Yt+1 = j + 1 | Yt = j) = 1/2
P(Yt+1 = j − 1 | Yt = j) = 1/2.
Define h(j) to be the expected number of steps to reach n starting at j. Write a system of linear equations with variables {h(j)}0≤j≤n.
(d) Use part (c) to verify that h(j) = n2 − j2.
(e) Given ϵ > 0, find a value of M such that, if a satisfied formula is given, our algorithm finds a valid assignment in the first M steps with probability at least 1 − ϵ.
Problem 3
Consider the d-Independent Set problem:
Input: an undirected graph G = (V, E) such that every vertex has degree less or equal than d.
Output: The largest Independent Set.
Describe a polynomial time algorithm A that approximates the optimal solution by a factor α(d). Your must write the explicit value of α, which may depend on d. Describe your algorithm in words (no pseudocode) and prove the approximation ratio α you are obtaining. Briefly explain why your algorithm runs in polytime.