Approximation Algorithm

Description:

• Polynomial time algorithms for an NP-hard problem X does not exist, unless P=NP
• Use to optimize finding a solution in NP-hard if the decision version of it is NP-complete
• Notation:
  • An optimization problem: X
  • Instance of X: x
  • solution of x returned by an algorithm A: A(x)
  • the value of a possible solution y of x: val(y)
  • the optimal value of instance x: Opt(x)
• example: knapsack problem ($O(2^n)$ or $O(nW)$), any solution with weight less than W is a solution but there can be only 1 optimal solution
• Difficulty:
  • Prove an approximation is guaranteed
  • Compare the solution return by the algorithm with an optimal solution that is computationally very hard to find

$\alpha$ approximation algorithm:

• An algorithm A is said to be an $\alpha$-approximation algorithm for an optimization problem X if for every instance x of X, A runs in poly-time and outputs a solution y such that:
  • val(y) $\ge \alpha$ Opt(x) if X is a maximization problem
  • val(y) $\le \alpha$ Opt(x) if X is a minimization problem
• $\alpha \le 1$ for maximization and $\alpha \ge 1$ for minimization problem
• If $\alpha$ is close to 1, then y is close to the optimum solution; $\alpha =1$ then A is the exact algorithm

Trade-offs:

• One of these 3 can not be guaranteed:
  • Runs in polynomial times
  • Solves arbitrary instances of the probnlem
  • Find optimal solution to problem
• $\alpha$-approximation algorithm:
  • Has polynomial run-time
  • Can solve arbitrary instances of the problem
  • Find solution whose value is within $\alpha$ of optimum

Techniques for designing approximation algorithms:

Greedy Algorithm:

• Fractional Knapsack Problem is $1/2$-approximation algorithm for KP
  • Proof. Let $x^{\star }$ (a 0-1 vector) be an optimal solution, and ${\mathrm{T}}^{\ast },\mathrm{T}$ be respectively the total profit of the optimal solution $x^{\ast }$ and the solution returned by the greedy
  • Let $j$ be the first item not included by the greedy algorithm.
  • The profit at that point is $\overline{p_j}=p_1+\cdots +p_{j-1}\le T$
  • The overall occupancy at this point is $\overline{w_j}=w_1+\cdots +w_{j-1}\le W$
  • We will show that ${\mathrm{T}}^{\ast }\le {\bar{p}}_j+p_j$
  • Hence, $\mathrm{T}\ge \max \left\{{\bar{p}}_j,p_j\right\}\ge 1/2{\mathrm{T}}^{\ast }$
  • Proof. We will show that ${\mathrm{T}}^{\ast }\le \overline{p_j}+p_j$
  • We have that ${\sum }_{i=1}^n{p}_i{x}_i^{\ast }\le {\sum }_{i=1}^{j-1}{p}_i{x}_i^{\ast }+{\sum }_{i=j}^n\frac{p_j{w}_i}{w_j}{x}_i^{\ast }=\frac{p_j}{w_j}{\sum }_{i=j}^n{w}_i{x}_i^{\ast }+{\sum }_{i=1}^{j-1}\left(p_i-\frac{p_j}{w_j}{w}_i\right)x_i^{\ast }$
    • $\begin{array}{rl}& \le \frac{p_j}{w_j}W+\sum _{i=1}^{j-1}\left(p_i-\frac{p_j}{w_j}{w}_i\right)=\sum _{i=1}^{j-1}{p}_i+\frac{p_j}{w_j}\left(W-\sum _{i=1}^{j-1}{w}_i\right)\\ & =\overline{p_j}+\frac{p_j}{w_j}\left(W-\overline{w_j}\right)\end{array}$
  • Since $w_j+\overline{w_j}>W$, we obtain ${\mathrm{T}}^{\ast }={\sum }_{i=1}^n{p}_i{x}_i^{\ast }\le \overline{p_j}+\frac{p_j}{w_j}\left(W-\overline{w_j}\right)\le \overline{p_j}+p_j$
• Load balancing
  • Instance: n identical machines, and m jobs, each job i having a processing time $p_i$
  • A machine can process at most one job at a time
  • Goal: The amount of processing time is as equal as possible, minimize the makespan, which is $\max \{T_1,T_2,...,T_n\}$
    • where $T_i$ is the processing time of ith machine
  • NP hard, reduced from Partition Problem
  • Let T* be optimal makespan
  • Solution:
    • List-scheduling:
      1. Consider m jobs in some fixed order.
      2. Assign job i to machine whose load is smallest so far
      • if the almost last job is very large, it would make the machine assigned to that job have large T while others will be small
      • Claims:
        • T* $\ge \max \{T_1,...,T_n\}\ge \max \{p_1,...p_m\}$
        • T* $\ge 1/2\{T_1+T_2\}$
        • proof: Total processing time of all jobs is T1 + T2 and Some machine must do at least half (or average) of the total workload
      • List-scheduling is a 2-approximation algorithm for lb
        • Proof. Suppose that machine 1 have the maximum load $T_1$, and let $j$ be the last job scheduled on machine 1
        • At the time j was scheduled, machine 1 must have had the least load; load on 1 before assigning job $\mathrm{j}$ is $T_1-p_j$
        • Since 1 has the least load, we know $T_1-p_j\le T_2$ and $T_1-p_j\le T_1$
        • $T_1-p_j\le 1/2\left(T_1+T_2\right)=1/2\left(p_1+\cdots +p_n\right)\le {\mathrm{T}}^{\star }$. Hence, $T_1=\left(T_1-p_j\right)+p_j\le 2.{\mathrm{T}}^{\ast }$
    • To improve: LPT rule:
      • Sort the jobs in descending order of processing time, and process jobs using greedy algorithm
      • Claim: If there are more than 2 jobs then T* $\ge 2p_3$ for 2 machines
      • Then it is $3/2$-approximation algorithm for LB
        • proof: Suppose that machine 1 have the maximum load $T_1$ and let $j$ be the last job scheduled on machine 1
        • If machine 1 has only one job then schedule is optimal
        • If 1 has at least 2 jobs, it must be the case that $j\ge 3$, or $p_j\le p_3\le 1/2{\mathrm{T}}^{\ast }$
        • Hence, $T_1=\left(T_1-p_j\right)+p_j\le {\mathrm{T}}^{\ast }+1/2{\mathrm{T}}^{\ast }=3/2.{\mathrm{T}}^{\ast }$

Linear programming:

Dynamic Programming