算法高级教程3.8ApproximationAlgorithmsbasedonlinearprogramming.pptVIP

Since is a concave function Let A(I) = weight of clauses that are satisfied. Corollary If each clause has length at least l, then Maximum Satisfiability: Best of Two Observation: Two approximation algorithms are complementary. – Johnsons algorithm works best when clauses are long. – LP rounding algorithm works best when clauses are short. John(I) RandomRoundingLP(I) k 1-2-k 1-(1-1/k)k 1 0.5 1.0 2 0.75 0.75 3 0.875 0.704 4 0.938 0.684 5 0.969 0.672 How can we exploit this? – Run both algorithms and output better of two. – Re-analyze to get 4/3-approximation algorithm. – Better performance than either algorithm individually! Max-k-SATBestoftwo(I) 1 ( ) ← Johnson(I) 2 ( ) ← RandomRoundingLP(I) 3 if then 4 return 5 else 6 return Lemma. For any integer Proof. Theorem The Max-k-SATBestoftwo(I) algorithm is a 4/3-approximation algorithm for MAX-SAT Proof. Duality Duality is a very important property. In an optimization problem, the identification of a dual problem is almost always coupled with the discovery of a polynomial-time algorithm. Duality is also powerful in its ability to provide a proof that a solution is indeed optimal. Given a linear program (LP) in which the objective is to maximize, we shall describe how to formulate a dual linear program (DLP) in which the objective is to minimize and whose optimal value is identical to that of the original linear program. When referring to dual linear programs, we call the original linear program the primal. Given a primal LP, if DLP is the dual LP of LP, then LP is the dual LP of DLP. Given a primal linear program (LP) in standard form, we define the dual linear program (DLP) as Subject to Primal-dual Primal: Subject to Subject to Dual: Now suppose we want to develop a lower bound on the optimal value of this LP. One way to do this is to find constraints that “loo