In the following blogs, we will focus on approximate algorithm. However, ahead of formally introdcuing this topic, we need to first introduce a strong tool that are useful in analysis and designing approximate algorithms – Linear Programing Problem and its dual problem.

LP Problem and Canonical Form

About the details of Linear Programming (LP) Problem that are introduced in my another series of blogs, if there is any doubt you can move here.

First, we will consider the “Canonical Form” of LP problem. That is

$$ \begin{equation} \begin{aligned} & \text{maximize} && \bar{c}^\top \bar{x} \\ & \text{subject to} && A \bar{x} \leq \bar{b} \\ & && \bar{x} \geq 0 \end{aligned} \end{equation} $$

In blogs of LP problem, we know we can transform any LP Problem to this “Canonical Form” (though this form are not mentioned in the blog, but we know the recipe of general form also works for it).

Addtionally, we know a lot of classic problem that can be formulated as LP Problem. Here, and in the following introduction of approximate algorithm, we will use “Set Cover” as an example.

Given Set Cover Problem, the universe set is ${ E =\{e_1,e_2,\cdots,d_n\} }$ and a series subsets ${ S_1,S_2,\cdots,S_m \subseteq E }$, and the cost of selecting ${ S_i }$ is ${ w_i }$ (For the non-weighted Set Cover Problem, we just need to set each ${ w_i }$ as ${ 1 }$.)

And, our objective is find ${ I \subseteq \{1,2,\cdots,m\} }$, such that ${ \bigcup_{i \in I} S_i = E }$ while minimizing the cost ${ \sum_{i\in I} w_i }$.

We can formulate above problem as Integer Linear Programming (ILP) Problem.

For each set ${ S_i }$, we set indicator variable ${ x_i }$ such that ${ x_i = 1 }$ if ${ S_i }$ is selected, otherwise ${x_i = 0 }$.

$$ \begin{equation} \begin{aligned} & \text{minimize} && \sum_{i = 1}^m x_i w_i \\ & \text{subject to} && \sum_{i \in \{j \mid e_j \in S_i\}} x_i, \forall e_j \in E \\ & && x_i \in \{0,1\} \end{aligned} \end{equation} $$

Dual Problem

Consider a Primal Linear Programming Problem

$$ \begin{equation} \begin{aligned} & \text{maximize} && c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ & \text{subject to} && a_{11} x_1 + a_{12} x_2 + \cdots +a_{1n} x_n \leq b_1 \\ & && a_{21} x_1 + a_{22} x_2 + \cdots +a_{2n} x_n \leq b_2 \\ & && \vdots \\ & && a_{m1} x_1 + a_{m2} x_2 + \cdots +a_{mn} x_n \leq b_m\\ \end{aligned} \end{equation} $$

We can multiply ${ y_i, i \in \{1,2,\cdots,m\} }$ to each constraint. And we can get the dual problem

$$ \begin{equation} \begin{aligned} & \text{minimize} && b_1 y_1 + b_2 y_2 + \cdots + b_m y_m \\ & \text{subject to} && a_{11} y_1 + a_{21} y_2 + \cdots +a_{m1} y_m \geq c_1 \\ & && a_{12} y_1 + a_{22} y_2 + \cdots +a_{m2} y_m \geq c_2 \\ & && \vdots \\ & && a_{1n} y_1 + a_{2n} y_2 + \cdots +a_{mn} y_m \geq c_n\\ \end{aligned} \end{equation} $$

Duality

Theorem 1 (Week Duality) A feasible solution to the dual LP is an upperbound on any feasible solution of primal LP.

Theorem 2 (Strong Duality) The optimal value of the dual LP is equal to the optimal value of primal LP.