Mathematics > QUESTIONS & ANSWERS > CSE_551_Graded_Quiz_8_Solutions. UPDATED 2022 (All)

CSE_551_Graded_Quiz_8_Solutions. UPDATED 2022

Document Content and Description Below

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

Last updated: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept: