算法高级教程3.7RandomapproximationAlgorithms.pptVIP

Randomization approximation algorithm Randomization approximation algorithm Let A be a randomized approximation algorithm for a minimization problem ∏, the performance ratio R(I) of the algorithm A on an input instance I is defined as where E(A(I))denotes the expected cost of the solution produced by the randomized algorithm A. Other definitions are similar to before. We also call a randomized approximation algorithm with absolute performance ratio R as randomized R-approximation algorithm. MAX satisfiability Given clauses C1, C2, . . ., Cn in CNF over Boolean variables x1, x2, . . . xm, and integer weights wj ≥ 0 for each clause, find a truth assignment for the xi that maximizes the total weight of clauses satisfied. Namely, NP-hard even if all weights are 1. MAX k-SAT: Every clause contains exactly k literals. MAX-3-CNF satisfiability All weights are 1. Every clause contains exactly 3 literals. Johnsons randomized Algorithm: Flip a coin, and set each variable true with probability ?, independently for each variable. Theorem Given an instance of MAX-3-CNF satisfiability, Johnsons Algorithm is a randomized 8/7-approximation algorithm. Proof Consider random variable Let Let OPT(I)=weight of the optimal assignment. R(I)=OPT(I)/E[A(I)] ≤n/(7n/8)=8/7. So R=8/7. Theorem Johnson’s algorithm is a 2-approximation algorithm for MAX-SAT. Proof Consider random variable Let Let OPT(I)=weight of the optimal assignment. R(I)=OPT(I)/E[A(I)] ≤n/(n/2)=2. So R=2. Corollary Johnsons algorithm is a 1/(1-(?)k)-approximation algorithm for MAX k-SAT Homework Exercises: Page 127 1,2 Problem Please improve Johnson‘s algorithms or design a randomized approximation algorithm for 3-SAT.