趨近算法 (Approximability)

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

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)))

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License