approximation

• 当input size很小时，我们可以解出来
• 有些special case可以在P内解出来。
• 可以找一个近似解。near optimal solution

an algorithm for a problem has an approximation ratio of $$\rho(n)$$ if: for input size n, 指标C表示该算法的结果，指标$C*$表示最佳值，那么我们有

$$max(\frac{C}{C^*}, \frac{C^*}{C}) \le \rho(n)$$

1 Vertex-cover

C={}, E'=G.E
while E' != {} {
pick an arbitrary edge (u,v) in E'
C += {u,v} // add u and v to C
从E'中去掉所有和u或v有关的边
}
return C


O(V+E)

1.1 证明这是2-ratio approximation solution

1. 可以在P内完成。
2. 对于选择的每条边(u,v)，设此集合为A。

2 Traveling-salesman problem

TSP with triangle constraint: NPC, but has 2-approximation solution TSP without triangle constraint: NPC, and no approximation unless P=NP

从G中随便找个点r



$$O(V^2)$$

2.1 证明2-approximation

$H*$为最佳值。此$H*$对应的hamilton cycle，减去某一条边，必然得一棵最小生成树。 设T为我们找到的树。显然有$$c(T) < c(H^*)$$.

$$\rho(n)=H(max{|S|, S \in F})$$

$$\sum_{S\in \phi^*} \sum_{x \in S} c_x \ge \sum_{x \in X} c_x = |\phi|$$

$$\sum_{x \in S} c_x = \sum_1^k (u_{i-1}-u_i) \frac{1}{|S_i-(S_1 \vee S_2 \ldots \vee S_{i-1})|}$$

$Si$是增加新cover最多的，所以$$|S_i-(S_1 \vee S_2 \ldots \vee S_{i-1})| \ge |S-(S_1 \vee S_2 \ldots \vee S_{i-1})| = u_{i-1}$$

\begin{eqnarray} & & \sum_{x \in S} c_x \le \sum_{i=1}^k (u_{i-1}-u_i) \frac{1}{u_{i-1}} \\ & = & \sum_1^k \sum_{j=u_i+1}^{u_{i-1}} \frac{1}{u_{i-1}} \\ & \le & \sum_1^k \sum_{j=u_i+1}^{u_{i-1}} \frac{1}{j} (because u_{i-1}>j) \\ & = & \sum_1^k(\sum_{j=1}^{u_{i-1}} \frac{1}{j} - \sum_{j=1}^{u_i} \frac{1}{j}) \\ & = & \sum_1^k (H(u_{i-1})-H(u_i)) \\ & = & H(u_0)-H(u_k) = H(u_0)-H(0)=H(u_0)=H(|S|) \end{eqnarray}

3.2 引理

$$\sum_1^n \frac{1}{i} = 1 + \sum_2^n \frac{1}{i} \le 1+ \int_1^n \frac{1}{x} dx = 1+ln(n)$$

4 Randomization and Linear Programming

Randomization for MAX-3-CNF satisfiability(n个变量，m个clause)

• 不含$xi$和$$\neg x_i$$
• 至少含1个变量

5 Linear Programming for weighted vertex cover

$$minimize \quad \sum_{v\in V} w(v)x(v) subject to \qquad x(u) + x(v) \ge 1 \qquad x(v) \in {0,1}$$

$$minimize \quad \sum_{v\in V} w(v)x(v) subject to \qquad x(u) + x(v) \ge 1 \qquad 0 \le x(v) \le 1$$

(1)的解都满足(2)，所以(2)的解是(1)的lower bound. 可以在P内得到(2)的解。

5.1 证明2-ratio

$$z^* = \sum w(v) \overline{x}(v) \ge \sum_{\overline{x}(v) \ge 1/2} w(v) \frac{1}{2} = \frac{1}{2} \sum_C w(v) = \frac{1}{2} w(c)$$

6 A fully polynomial time approximation scheme for subset sum

Problem: <s,t> 从S中找一个子集，使其sum尽量大，但不大于t。

EXACT-SUBSET-SUM(S,t)

let L[i] denote x[0]-x[i]的所有sum可能性(<=t的)。

L[0] = {0}
for i=1 to n
L[i] = MergeList(L[i-1], L[i-1]+x[i])
L[i].remove(x[i]>=t)
return largest in L[n]


6.1 a fully polynomial time approximation scheme

TRIM(L,delta)

L' = {y}
last = y
for i = 2 to m
if y[i] > last * (1+delta)
L' += y[i]
last = y[i]


APPROX-SUBSET-SUM(S,t,epsilon)

L[0] = {0}
for i=1 to n
L[i] = MergeList(L[i-1], L[i-1]+x[i])
L[i] = TRIM(L[i], epsilon/2n)
L[i].remove(x[i]>=t)
return largest in L[n]


6.2 证明此算法是a fully polynomial time approximation scheme

Denote:

• $$z^*$$: 我们的值
• $$y^*$$: 真正的值
• $$P_i$$: $x0 ~ xi$相加的氖可能性
• $$L_i$$: 迭代中产生的

1. 是$(1+ε)$-ratio的
2. running time is P to both $$\frac{1}{\epsilon}$$ and n

6.2.1 1

$$f(n)=(1+\frac{a}{n})^n ln(f(n)) = n ln(1+\frac{a}{n}) \frac{f'(n)}{f(n)} = ln(1+\frac{a}{n}) - \frac{a}{n+a}$$

$$ln(1+\frac{a}{n}) = ln(\frac{n+a}{n}) = ln(x) |_n^{n+a} = \int_n^{n+a} \frac{1}{x}dx$$

$$(1+\frac{\epsilon}{2n})^n \le e^{\frac{\epsilon}{2}} \le 1+\frac{\epsilon}{2} + (\frac{\epsilon}{2})^2 \quad (3.13) \le 1+\epsilon$$

#### 证明(1)

1. y是某一个y'

1. y是某一个$$y'+x_i$$

$$\frac{y}{(1+\delta)^i} = \frac{y'+x_i}{(1+\delta)^i} \le \frac{z'}{1+\delta} + \frac{x_i}{(1+\delta)^i} \le \frac{z'}{1+\delta} + \frac{x_i}{1+\delta} \le z$$

#### 2 因为trim的原因，那么在Li中两个数之间要大于$1+\frac{\epsilon}{2n}$倍。 所以Li中共有$⌊ log1+\frac{\epsilon}{2n} t ⌋+2$个数（加0和1）。

$$log_{1+\frac{\epsilon}{2n}} t +2 = \frac{ln(t)}{ln(1+\frac{\epsilon}{2n})} +2 \le \frac{2n(1+\frac{\epsilon}{2n})ln(t)}{\epsilon} +2 \le \frac{3nln(t)}{\epsilon}+2$$