# 訊息

## English

``````Chapter 13 Approximability

F(x) : feasible solution instance set.
OPT(x) = minx in F(x)c(s)  for minimization problem
= maxx in F(x)c(s)  for maximization problem

εapproximation algorithm :
M is anεapproximation algorithm iff x
|c(M(x))-OPT(x)|/max{OPT(x), c(M(x))} ≦ ε

Approximation threshold for A: greatest lower bound of εfor A

Theorem :
1. The lower bound of k-MAXGSAT is at most 1-1/2^k
2. The lower bound of MAXSAT     is at most 1/2
3. The lower bound of MAXSAT with k distinct literal is at most 1/2^k

Theorem : NP-complete = R Hamilton <R TSP(1-ε)
Proof :
G = (V,E)
dist(u,v) =
if (u,v) in E
then dist(u,v) = 1
else dist(u,v) = |V|/(1-ε)
so :
TSP(dist) has (1-ε) approximation threshold iff Hamilton in P

Theorem : The approximation threshold of KNAPSACK is 0.
(ε>0 there is a polynomial approximation algorithm for KNAPSACK)
Proof :
dual problem : W(i+1,v) = min{W(i,v), W(i,v-vi+1)+Wi+1}
S=(v1,.., vn) truncate b bit -> (v1’,..,vn’)=S’

Σvi ≧ Σvi ≧ Σvi’ ≧ Σvi’ ≧ Σ (vi-2^b) ≧ Σvi-n*2^b
i in S  i in S’ i in S’  i in S   i in S          i in S

let ε = n*2^b/V => b = log(εV/n)

(R,S) is L-Reduction from A to B iff
OPT(R(x)) ≦ α*OPT(x), where x in A, R(x) in B
|OPT(x) - c(S(s))| ≦ β*|OPT(R(x))-c(s)| , where s in R(x)

Theorem : L-reduction is transitive
A -(R,S)-> B -(R’,S’) -> C
A -------(RR’,SS’)-----> C

Theorem : if A - (R(α),S(β)) -> B, and εapproximate for B then
αβε/(1-ε) approximate for A
Proof :
x in A, y in B
OPT(R(x)) ≦ α*OPT(x)
c(M(R(x)))```
```