Computer Science > QUESTIONS & ANSWERS > CSE 551: Quiz 8 Solutions (All)

CSE 551: Quiz 8 Solutions

Document Content and Description Below

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 assig ... nment 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]

Last updated: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept: