From this blog, we begin to focus on approximation algorithms. And, this blog will talking about the defnition of approximation alogirthm and the techniques of analysis through Linear Programming.

${ \alpha }$-approximation algorithm

An ${ \alpha }$-approximation algorithm for an optimization problem is a polynomial-time algorithm that for all instances of the problem produces a solution for which the value is within a factor of ${ \alpha }$ of the value of an optimal solution.

For ${ \alpha }$-approximation algorithm, that means:

1. The algorithm runs in polynomial time.

2. The algorithm always produces a feasible solution.

3. The value is within a factor ${ \alpha }$ of the value of an optimal solution. (Here, ${ \alpha >1 }$, ${ OPT(I) }$ means the optimal solution of instance ${ I }$, and ${ A(I) }$ means the value generated by approximation algorithm ${ A }$ of instance ${ I }$.)

   • For max optimization ${ \frac{OPT(I)}{A(I)} \leq \alpha }$

   • For min optimization ${ \frac{A(I)}{OPT(I)} \leq \alpha }$

And a common stratege for prove an approximation algorithm within a factor ${ \alpha }$ is (take min optimazation as an example):

1. Find an lower bound ${ u }$ of ${ OPT }$, that is ${ OPT \geq u }$

2. Find an upper bound ${ l }$ of ${ A }$, that is ${ l \geq A }$

3. Prove ${ l \leq \alpha u }$, that is ${ A \leq l \leq \alpha u \leq OPT }$

LP techniques (Vertex Cover as Example)

Let’s consider vertex cover problem.

Give a graph ${ G=(V,E) }$, find a subset of vertices ${ S \subseteq V }$, such that each edge has an endpoint in the set ${ S }$. Our goal is to minimize ${ \vert S \vert }$.

Algorithm ${ \mathcal{A} }$

Find a maximal matching ${ M }$ and add all endpoints of the edges in ${ M }$ to ${ S }$.

Steps: Choose the edges one by one (if the egde is compatiable to already-selected edges) until no edges can be added anymore.

Therorem: Algorithm ${ \mathcal{A} }$ is a ${ 2 }$-approximation algorithm of Vertex Cover Problem.

Proof.

1. Polynomial run-time: It’s clear to see the number of loops is ${ O(\vert E \vert ) }$.

2. Feasibility: Suppose there exists edge ${ e \in E }$ that is not covered, that means both endpoints of ${ e }$ are not in ${ S }$. So ${ e\notin M }$. Then we can add ${ e }$ to ${ M }$, because ${ e }$ don’t have any overlap endpoints with ${ M }$. So, we get a bigger matching which contradicts to ${ M }$ is maximal matching.

3. ${ 2 }$-approximation:

   • The edges in ${ M }$ can not share endpoints to each other, that implies ${ \vert S \vert = 2 \vert M \vert }$.
   • The optimal vertex cover needs to cover all the edges in ${ M }$, that means the optimal solution have to contain at least one endpoint of each edge in ${ M }$. And all edges in ${ M }$ can not share endpoints to each other. So ${ OPT \geq \vert M \vert }$
   • ${ \vert S \vert = 2 \vert M \vert \leq 2 OPT }$, that is ${ \frac{S}{OPT} \leq 2 }$

Hence, Algorithm ${ \mathcal{A} }$ is a ${ 2 }$-approximation algorithm. ${ \square }$

Algorithm ${ \mathcal{B} }$

First we formulate the vertex cover problem as Integer Linear Programming (ILP)

For each vertex ${ v_i \in V}$, we set indicator variable ${ x_i \in \{0,1\} }$ to represent if we selected vertex ${ v_i }$.

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{\vert V \vert } x_j \\ &\text{subject to} && x_i + x_j \geq 1, \quad \forall e =\{v_i,v_j\} \in E\\ & && x_j \in \{0,1\} \end{aligned} \end{equation} $$

ILP cannot be solved in polynomial time, then we relax it to LP Problem.

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{\vert V \vert } x_j \\ &\text{subject to} && x_i + x_j \geq 1, \quad \forall e =\{v_i,v_j\} \in E\\ & && x_j \geq 0 \end{aligned} \end{equation} $$

But after solving LP Problem, some of the decision variables are fractions. Hence we need to decide each variable is set to ${ 0 }$ or ${ 1 }$. In other words, how to decided the threshold. The way to decide the threshold will induce to many different approximation algorithms. Here, we set threshold as ${ 1/2 }$ (Because we have constrain ${ x_i + x_j \geq 1 }$ need to satisify, we will show it in detail in next proof). Here, we denote the optimal solution as ${ x_1^*, x_2^*, \cdots, x_n^* }$, and the integer solution as ${\hat{x}_1,\hat{x}_2,\cdots,\hat{x}_n}$

Theorem: Algorithm ${ \mathcal{B} }$ is a ${ 2 }$-approximation algorithm for Vertex Cover Problem.

Proof.

1. Polynomial Run-time: the relexed LP problem can be solved in polynomiak time and the seting each decision variable to integer takes ${O(n)}$ time.

2. Feasibility: For each edge ${ e= (i,j)}$, we have to meet the constraint in relaxed LP problem, that is ${x_i^*+x_j^* \geq 1}$. So, we have either ${x_i^* \geq 1/2}$ or ${x_j^* \geq 1/2}$ (otherwise ${ x_i^*+x_j^* \leq 1 }$).

3. ${ 2 }$-approximation: for each ${ \hat{x_j} }$, if ${ x_j^* \geq 1/2 }$, ${ \hat{x_j} = 1 }$, else ${ \hat{x_j} = 0 }$. And we know the minimum value of ILP ${ Z^*_{ILP} }$ will not less than the minimum value of LP ${ Z^*_{LP} }$ (because the feasible region of ILP is the subset of the feasible region of LP). Hence, we have

$$ \vert S \vert = \sum_{j=1}^n \hat{x}_j \leq 2 \sum_{j=1}^n x^*_j = 2Z^*_{LP}\leq 2 Z^*_{ILP} = 2 OPT $$

Hence we prove that Algorithm ${ \mathcal{B} }$ is a ${ 2 }$-approximation algorithm. ${ \square }$

Algorithm ${ \mathcal{B} }$ for weighted vertex cover

Considering the weighted vertex cover problem, we assign a weight to each vertex and want to minimize the total weight of vertex cover.

Now we can consider the ILP problem as below

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{\vert V \vert } w_j x_j \\ &\text{subject to} && x_i + x_j \geq 1, \quad \forall e =\{v_i,v_j\} \in E\\ & && x_j \in \{0,1\} \end{aligned} \end{equation} $$

And the relaxed LP problem as

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{\vert V \vert } w_j x_j \\ &\text{subject to} && x_i + x_j \geq 1, \quad \forall e =\{v_i,v_j\} \in E\\ & && x_j \geq 0 \end{aligned} \end{equation} $$

We can use Algorithm ${ \mathcal{B} }$ for weighted vertex cover problem, and we can prove it’s still a ${ 2 }$-approximation algorithm by similar proof.

$$ \sum_{j\in S} w_j = \sum_{j=1}^n w_j \hat{x}_j \leq 2 \sum_{j=1}^n w_j x^*_j = 2Z^*_{LP}\leq 2 Z^*_{ILP} = 2 OPT $$