CSE 551: Quiz 8 Solutions[ALREADY PASSED]

Document Content and Description Below

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 satis ed in . Suppose we have invented an approximation algorithm that nds 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 nds 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: 1 year ago

Preview 1 out of 8 pages