Question 1. Let A[1], . . . , A[2k] be a list of values that are sorted in increasing order. Your goal is find the i ∈ [k] such that f(i) = A[i + k] − A[i] is maximized. Unfortunately you don’t have time to test all k pairs but luckily you are happy with an approximate solution. (1) Design a 2-approximation that only requires reading O(1) values from the list. (2) Design a (1 + )-approximation that only requires reading O( −1 log k) values from the list. Hint: For the first part consider reading A[1], A[k], A[k + 1], and A[2k]. For the second part, one possible approach involves performing O(1/) binary searches. Remember to analyze the running time and prove the approximation ratio.

Question 2. Let G = (V, E) be an undirected graph in which each node has degree at most d. Design a polynomial time algorithm that finds an independent set whose size is at least 1/(d + 1) times that of the largest independent set. Remember to analyze the running time and prove the approximation ratio.

Question 3. The input to the Min-Squares problem is a set of positive integers x1, . . . , xn, r and L. We want to know if it is possible to partition x1, . . . , xn into r sets S1, S2, . . . , Sr such that Xr i=1 ï£« ï£ X x∈Si x ï£¶ ï£¸ 2 ≤ L . Prove that Min-Squares is NP-Complete via a reduction from SubsetSum.

Question 4. Design (and analyze) a factor 4 approximation algorithm for Min-Squares, i.e., minimizing Pr i=1 P x∈Si x 2 . Hint: For Q3 and Q4, note that Pr i=1 P x∈Si x 2 ≥ r ( Pn i=1 xi/r) 2 .

Question 5. In the Best-Sat problem, we are given a set of OR-clauses, and we want to find an assignment that satisfies as many as possible. You may assume that the variables involved in each clause are distinct, i.e., you can’t have a clause like x1 ∨ x2 ∨ x¯2 ∨ x3. (1) Randomly set each variable to true or false by flipping a coin. Suppose the input has m clauses, of which the jth has kj literals. What is the expected number of clauses satisfied as a function of k1, . . . , km? Show that if all clauses contain exactly k literals, then the ratio between the optimal value and the expected number of satisfied clauses is ≤ 1 + 1/(2k − 1). (2) Can you make this algorithm deterministic? Hint: Instead of flipping a coin for each variable, select the value that satisfies the most of the as-of-yet unsatisfied clauses.

Question 6. The input to demi3sat is a 3sat formula φ. The output should be “yes” iff there is a satisfying assignment for φ such that exactly half the variables are set to “true”. Prove that demi3sat is NP-complete.

Subject | Computer |

Due By (Pacific Time) | 12/04/2015 12:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |