近似¶

概念¶

近似比：
- max(A(I)/opt(I) , opt(I)/A(I)) <= \(\rho\)(|I|)，则称其为\(\rho\)(n)近似的算法
A polynomial-time approximation scheme(PTAS)
- PTAS：关于n为多项式
- FPTAS：关于1/ϵ也为多项式

例子¶

Binpack problem（NP-hard）¶

input：n items with sizes s1~sn
output：用尽可能少的箱子装（箱子容量固定）
Next fit：顺序装，装不下封箱下一个
- NF用的箱子数，opt最优解箱子数
- NF/opt <= 2：近似比
- 2-approximation算法
Any fit：for一遍，当前打开的箱子可以装就装，不能就开一个新的
- First fit：找第一个
- Best fit：找装的最满的
- BF(I)&FF(I) <= 1.7opt(I)，即近似比为1.7
  - 绝对近似比
First/Best fit decreasing:
- 先对item排序
- BFD(I)&FFD(I) <= 11/9 opt(I) + 6/9
  - 渐进近似比为11/9
  - 绝对近似比，在 opt(I) 取2时得，为1.5
NP复杂度最优近似比1.5，要求online则最优5/3

Knapsack problem(背包问题)¶

Input：n items (v1,w1)~(vn,wn)，容量C
output：最大化总价值的背包装法
- O(nC)或O(nV_sum)，伪多项式
分数版本：可以选零点几个物品
- 按性价比贪心
整数版本（NPhard）
- 贪心算法
  - on vi/wi（性价比）
    - 被小物件卡，选不了高价值大物件
    - OPT/A>=(C-1)/2
  - on vi（价值）
    - 被大物件卡，选不了高性价比小物件
    - OPT/A>=C-1
  - 两种算法存在缺点，但互补
- A*：A1和A2各跑一遍选最优
  - A1 >= OPT_分数版本 - Vmax
  - A2 >= Vmax
  - 则2A* >= OPT_frac >= OPT
  - A* >= OPT/2
- 优化：所有v除以一个d
  - 原本O(\(n^2V_{sum}\))
  - d=gcd(v1...vn)，则不影响结果
  - d= \(\lceil nV_{sum}/\delta\rceil\) ，则O(\(n^3 / \delta\))
  - 求出近似比为\(1/1-\delta\)

K-center problem¶

Input：n site s1...sn，整数k
output：找到k个center，盖住所有sites并使得半径最小
dist(x,c)=\(min_{y\sub C}\) (dist(x,y))
k=1：随便选一个site作为center，近似比为2
已知最优解：
- 若存在未覆盖site，选为site，然后去掉覆盖的site
- 循环最多进行k次
- 所以假定一个解（二分）
贪心
- 选一个site作为center
- 一直选择距离center最远的site作为新的center
- 得到最终的center集合Ck
- r(Ck)<=2r*

习题¶

1.Suppose ALG is an α-approximation algorithm for an optimization problem Π whose approximation ratio is tight. Then for every ϵ>0 there is no (α−ϵ)-approximation algorithm for Π unless P = NP. F, 按照我的理解，可能会有近似比更小的算法。

2.As we know there is a 2-approximation algorithm for the Vertex Cover problem. Then we must be able to obtain a 2-approximation algorithm for the Clique problem, since the Clique problem can be polynomially reduced to the Vertex Cover problem. T， reduce to 就算<=，如果CP<=VC, VC有近似比为2的算法，那么CP也有

3.For the bin-packing problem: let S=∑Si. Which of the following statements is FALSE?

A.The number of bins used by the next-fit heuristic is never more than ⌈2S⌉

B.The number of bins used by the first-fit heuristic is never more than ⌈2S⌉

C.The next-fit heuristic leaves at most one bin less than half full

D.The first-fit heuristic leaves at most one bin less than half full

NF近似比是2，其他的近似比都比2小。Next fit可能有多个半空的bit，因为如果永远往前放，不会回头放之前的，所以是C，而FF会检查之前所有位，因此如果有两个半空的，它们会放在一起。

4.To approximate a maximum spanning tree T of an undirected graph G=(V,E) with distinct edge weights w(u,v) on each edge (u,v)∈E, let’s denote the set of maximum-weight edges incident on each vertex by S. Also let w(E′)=∑(u,v)∈E′， w(u,v) for any edge set E′. Which of the following statements is TRUE?

A.S=T for any graph G

B.S≠T for any graph G

C.w(T)≥w(S)/2 for any graph G

D.None of the above

C, 题目的意思是，如果把每个点最大权值的边加入一个集合，那么这个集合的权值和最大生成树权值之比是多少。注意，点的最大权值边集合意味着集合里相同的边最多出现一次。

很容易证明，S里面不存在环，因此T一定包含S.所以w(T)>=w(S)

假如存在环，设边为e1,e2,e3,…ej, 点为p1, …pj

由于e1在S中，因此w(e1)>w(ej)，由于e2在S中，因此w(e2)>w(e1),…，最后得到的是w(ej)>w(e1)，矛盾。

5.Assume that you are a real world Chinese postman, which have learned an awesome course “Advanced Data Structures and Algorithm Analysis” (ADS). Given a 2-dimensional map indicating N positions pi(xi ,yi) of your post office and all the addresses you must visit, you’d like to find a shortest path starting and finishing both at your post office, and visit all the addresses at least once in the circuit. Fortunately, you have a magic item “Bamboo copter & Hopter” from “Doraemon”, which makes sure that you can fly between two positions using the directed distance (or displacement).

Bamboo.jpg (“Bamboo copter & Hopter”, japan12.com/bamboo-copter-hopter)

However, reviewing the knowledge in the ADS course, it is an NPC problem! Wasting too much time in finding the shortest path is unwise, so you decide to design a 2−approximation algorithm as follows, to achieve an acceptable solution.

Compute a minimum spanning tree T connecting all the addresses. Regard the post office as the root of T. Start at the post office. Visit the addresses in order of a _____ of T. Finish at the post office. There are several methods of traversal which can be filled in the blank of the above algorithm. Assume that P≠NP, how many methods of traversal listed below can fulfill the requirement?

Level-Order Traversal Pre-Order Traversal Post-Order Traversal

A.0

B.1

C.2

D.3

C，不知道题目再说什么

6.An approximation scheme that runs in O(n^2/ϵ) for any fixed ϵ>0 is a fully polynomial-time approximation scheme.

T, 如果1/ϵ也是多项式级别的，那么就算是full

7.An approximation scheme that runs in O(n^2 3^ϵ) for any fixed ϵ>0 is a polynomial-time approximation scheme.

T, 只要是n是多项式级别的就可以。

8.In the bin packing problem, we are asked to pack a list of items L to the minimum number of bins of capacity 1. For the instance L, let FF(L) denote the number of bins used by the algorithm First Fit. The instance L′ is derived from L by deleting one item from L. Then FF(L′) is at most of FF(L).

F, 如果是NF则是F, yds说的。

9.For the 0-1 version of the Knapsack problem, if we are greedy on taking the maximum profit or profit density, then the resulting profit must be bounded below by the optimal solution minus the maximum profit.

Popt<Pfrac<Pgre+pmax，最优解一定小于物体可分情况下的解。而物体可分情况下的解，可以看成greedy的解+一部分不完整的物体。不完整的物体权值一定小于最大权值。

(感觉证明有问题)

10.An (1+ϵ)-approximation scheme of time complexity (n+1/ϵ)^3 is a PTAS but not an FPTAS.

F