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 th
...
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.
[Show More]