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