CSC373, Winter/Spring 2020 Assignment 4 Due: Thursday, April 16, 2020 4:59PM on MarkUs You will receive 20% of the points for any (sub)problem for which you write “I do not know how to answer this question.” You will receive 10% if you leave a question blank. If instead you submit irrelevant or erroneous answers you will receive 0 points. You may receive partial credit for the work that is clearly “on the right track.” You may choose to spend your time looking for solutions on the internet and may likely succeed in doing so but you probably won’t understand the concepts. So at the very least try to do the assignment initially without searching the internet. If you obtain a solution directly from the internet, you must cite the link and explain the solution in your own words to avoid plagarizing. Note: As we had to change the grading scheme, it is especially important that you work individually. In particular you should not take a solution from someone else. However, it is permissable to discuss a problem with other students so as you are learning together. But then you should wait at least one hour before writing down your solution and you should not use any written notes from conversations with other students. Just keep in mind that the goal is to understand the concepts. It is always important not to plagarize but if we are going to increase the weight of assignments, we clearly have to have some confidence that your work is your work. 1. (20 points) Consider again the weighted set packing problemi as in Assignment A3. The input is a collection C = {S1, S2, . . . , Sm} of sets where |Si| ≤ k for some fixed integer k and wi is the weight of Si. The objective is to select a subcollection C ′ of disjoint sets so as to maximize ∑ Si∈C′ wi. Consider the oblivious local search algorithm LOCAL that for any current solution C ′, tries to add a set Si ∈ C \ C ′, removing any Sj ∈ C ′ that intersects Si. The algorithm stops when there is no such Ci ∈ C \ C ′. Initially, we can set C ′ = ∅ or Si for any single set Si. Show that LOCAL achieves a k approximation ratio. That is, for every input C, LOCAL(C) ≥ 1 k OPT (C). Use a charging argument to show that your algorithm obtains the stated approximation. 2. (20 points) Consider the Exact Max-2-SAT problem and the oblivious local search algorithm with Hamming distance neighbourhood N1(τ) as defined in the slides for week 10. This al- gorithm achieves approximation (totality) ratio 2 3 . Suppose we extend the neighbourhood of any truth assignment to N ′1(τ) = N1(τ) ∪ {τ} where τ is the complement truth assignment; that is, τ = true iff τ = false. Prove that the same oblivious local search algorithm using neighbourhood N ′1 acheives an approximation (totality) ratio of 3 4 . Note: You can just consider the unweighted problem as the proof for the weikghted problem would be the same. You will receive reasonable credit if you can argue why this extended neighbourhood will help improve the totality ratio knowing what you know about the analysis for the N1 neighbourhood. 1 of 2 CSC373, Winter/Spring 2020 Assignment 4 3. (20 points) Consider the following weighted Max-Sat problem: We are given a weighted CNF formula F = C1 ∧ C2 ∧ . . . ∧ Cm where each clause Ci has a positive integer weight wi. Furthermore, all the clauses in F have either 3 or 4 literals and that ∑ i:Ci has 3 literalswi = ∑ i:Ci has 4 literalswi. The goal is to find a truth assignment so as to maximize the weight of satisfied clauses. Provide a polynomial time randomized algorithm whose objective is to maximize in expecta- tion the weight of satisfied clauses. What guarantee can you provide on the expected weight of satisfied clauses. Explain your answer. 4. (20 points) Consider two polynomial size (i.e., number of aritmetic operations) arithmetic circuits C1 and C2 each having operations +,−,× and inputs x1, x2, . . . , xn, c1, . . . cm where the ci ≤ n are constants in N. Furthermore, the circuits have depth O(log n). The output of these circuits are polynomials P1(x1, . . . xn) and P2(x1, . . . , xn). We say that two such circuits are equivalent (denoted C1 ≡ C2) if P1 and P2 are identical multivariate polynomials. For example, (x1 − x2) · (x1 + x2) ≡ x21 − x22. Describe a 1-sided error randomized polynomial (in n) time algorithm ALG that will determine if C1 ≡ C2 with high probability. Namely, ALG must satisfy the following: • If C1 ≡ C2, then ALG will say YES • If C1 6≡ C2, then ALG will say NO with probability at least 1− 2−n. 5. (20 points) We have posted on the 373 web page, lecture notes by Dan Spielman (Yale University) on Schoning’s algorithm for 3SAT. Those notes start with a slighlty different al- gorithm and somewhat simpler analysis resulting in a 1-sided error randomized O˜(2 3 2 ) time bound (say with constant error probability) where O˜ hides logarithmic factors. The slides then show how to obtain Schoning’s algorithms obtaining time O˜(2 4 3 ). In this exercise you are to adapt the simpler analysis for the 4-SAT problem. What is your time bound? 2 of 2
