CSE 551: Quiz 8 Solutions
Jamison Weber
August 14, 2020
Problem 1
Consider the MAX-SAT problem, where we are given a boolean formula Φ in
conjunctive normal form (i.e. a conjunction of disjoint literals), and we seek
a satisfying assignment of variables that maximizes the number of clauses
satisfied in Φ. Suppose we have invented an approximation algorithm that
finds a suboptimal solution to the MAX-SAT problem and I have somehow
proven that this algorithm is a ρ-approximation of the optimal solution.
What can one then conclude about the value of ρ?
• 0 < ρ < 1
• ρ = 1
• ρ > 1
• Nothing meaningful can be concluded about the value of ρ from the
information provided.
Rationale
The key observation here is that the MAX-SAT problem is a maximization
problem, therefore any value of ρ would need to be strictly between 0 and 1.
If ρ > 1, then one is essentially claiming the algorithm finds a solution better
than optimal, which is a contradiction. If ρ = 1, one is essentially saying
the algorithm is optimal, and is therefore not an approximation algorithm.
1
Problem 2
Consider an arbitrary, connected, weighted graph. The professor presents
this graph to her students and tasks them with finding whether there exists
a hamiltonian cycle of a certain total weight. To which complexity class
does this task belong?
• It is strictly NP-complete since it is a decision problem to which
all problems in NP can be reduced and the problem is in NP.
• It is strictly NP-Hard since it is a combinatorial optimization problem.
for which no polynomial time algorithm is currently known.
• It is in P since the problem can be solved in polynomial time.
• It is in NP but not NP-complete since there exists a polynomial time
certifier for any instance of the problem.
Rationale
The class NP is entirely made of decision problems, which this problem
formulation conforms to. Also, the decision version of the traveling salesman problem has been shown to be NP-Complete, so statement 1 is correct.
Statement 2 is false. If the professor asked for the lowest weight hamiltonian cycle, then this problem would be strictly NP-Hard since it is not
known whether a polynomial time certifier exists. To determine whether
a certificate solution is correct, one would have to compare it to all other
hamiltonian path solutions. A hamiltonian cycle solution can be represented
as a permutation of nodes, thus this would require n! comparisons in the
worst case. Statement 3 is false, since no polynomial time algorithm is
known to be capable of solving this problem. Statement 4 is false, as it has
been demonstrated above that the problem is NP-complete.
Problem 3
Recall the proof of correctness for the 2-approximation algorithm that solves
the traveling salesman problem seen in lecture. Which of the following
statements justifies the claim w (TSP) ≤ 2w (MST)? Assume all positive
edge weights.