Approximation Algorithm

1. Approximation ratio

Cost: the size of the solution, for example, in vertex cover, it’s the size of the cover; in TSP, it’s the total distance.

Since the approximation algorithm, the cost we have is always greater than the optimal solution.

Running time: O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣), loop over all edges and all vertices.
∣ A ∣ |A| ∣A∣: the number of edges chosen by the algorithm, and since one edge covers two vertices, so ∣ A ∣ = ∣ C ∣ / 2 |A|=|C|/2 ∣A∣=∣C∣/2. And since this is an approximation algorithm, and at least one of vertices chosen each time must be in C C C, thus ∣ C ∣ |C| ∣C∣ must be greater than the edges chosen by the algorithm.

Construct a minimum spanning tree, whose sum of edge weights is as small as possible.
Remember to skip duplicates;
Proof to the theorem:
- Since the distance in MIS is less than the distance in TSP; c ( T ) ≤ c ( H ∗ ) c(T)\le c(H^*) c(T)≤c(H∗)
- the sum of weights in Euler tour is twice the sum in MIS, since we go through each vertex twice; c ( W ) = 2 c ( T ) c(W)=2c(T) c(W)=2c(T)
- the sum of weight returned by the algorithm is less than the sum of Euler tour, since we will skip duplicates: c ( H ) ≤ c ( W ) c(H)\le c(W) c(H)≤c(W)
- Above all, we have: c ( H ) ≤ 2 c ( H ∗ ) c(H)\le 2c(H^*) c(H)≤2c(H∗).

Find a set of subsets, which can cover the big set.

Intuition: each time pick the remaining largest subset, until the set is covered.

∣ X ∣ |X| ∣X∣: the size of the big set.

c x : c_x: cx: if element x x x is covered for the first time by S i S_i Si;

c x = 1 ∣ S i − ( S 1 ∪ S 2 ∪ . . . ∪ S i − 1 ) ∣ c_x=\frac{1}{|S_i-(S_1\cup S_2\cup...\cup S_{i-1})|} cx=∣Si−(S1∪S2∪...∪Si−1)∣1
∑ x ∈ S i − S < i c x \sum_{x\in S_i-S_{<i}}c_x ∑x∈Si−S<icx: sum up the vertices in each subset;
intuition: sum up the vertices in each chosen subset and sum up all the subset, it’s exactly the size of subsets returned by the algorithm; each time the algorithm assigns 1 unit of cost.

Double count the c x c_x cx in C ∗ C^* C∗, and with the lemma above, we then prove the theorem. Notice: H ∣ S ∣ ≤ H ∣ X ∣ H_{|S|}\le H_{|X|} H∣S∣≤H∣X∣.
Proof for the lemma:
u i u_i ui the number of vertices that are not covered after step i i i; u 0 = ∣ X ∣ u_0=|X| u0=∣X∣, u k = 0 u_k=0 uk=0, where k k k is the last step.
u i − 1 − u i u_{i-1}-u_i ui−1−ui the number of elements covered by step i i i;
∑ j = u i + 1 u i − 1 \sum_{j=u_i+1}^{u_{i-1}} ∑j=ui+1ui−1: the number of elements first covered by step i i i;
since j ≤ u i − 1 j\le u_{i-1} j≤ui−1, and 1 over j j j must be greater than 1 u i + 1 \frac{1}{u_i+1} ui+11.
there are some cancelations in the sum in brackets.

Give the definition of c x c_x cx: the number of elements covered for the first time in step i i i divided by 1;
Thus, if we sum up all the elements covered for the first time, that would be the number of elements covered by the algorithm: ∣ C ∣ = ∑ x ∈ X ∣ C ∣ c x = ∑ i = 1 ∣ C ∣ ∑ x ∈ S i − S < i c x = ∑ i = 1 ∣ C ∣ 1 |C|=\sum_{x\in X}^{|C|}c_x=\sum_{i=1}^{|C|}\sum_{x\in S_i-S_{<i}} c_x=\sum_{i=1}^{|C|}1 ∣C∣=∑x∈X∣C∣cx=∑i=1∣C∣∑x∈Si−S<icx=∑i=1∣C∣1;
Each element x ∈ X x\in X x∈X, is in at least one set in the optimal cover C ∗ C^* C∗, thus: ∑ S ∈ C ∗ ∑ x ∈ S c x ≥ ∑ x ∈ X c x \sum_{S\in C^*}\sum_{x\in S}c_x\ge \sum_{x\in X}c_x ∑S∈C∗∑x∈Scx≥∑x∈Xcx;
Then we have: ∣ C ∣ ≤ ∑ S ∈ C ∗ ∑ x ∈ S c x |C|\le\sum_{S\in C^*}\sum_{x\in S}c_x ∣C∣≤∑S∈C∗∑x∈Scx
Simplify the proof for the lemma:
- ∑ x ∈ S c x = ∑ i = 1 ∣ C ∣ ∑ x ∈ S ∩ ( S i − S < i ) c x \sum_{x\in S}c_x=\sum_{i=1}^{|C|}\sum_{x\in S\cap(S_i-S_{<i})}c_x ∑x∈Scx=∑i=1∣C∣∑x∈S∩(Si−S<i)cx: the subscript of the sum: the elements that are not covered after step i i i;