Approximation Algorithm

⭐文章目录⭐

• Approximation Algorithm
  • Bin Packing Problem
  • Knapsack Problem
  • K-Center Problem

👇

Approximation Algorithm

Definition

• For any instance $I$:
  • Find an optiomal solution(ignored)
  • In poly($|I|$) time

An algorithm has an approximation ratio of $\rho (n)$ if, for any input of size $n$, the cost $C$ of the solution produced by the algorithm is within a factor of $\rho (n)$ of the cost $C’$ of an optimal solution:

$$max\lbrace\frac{C’}{C},\frac{C}{C’}}\leq \rho (n)$$

If an algorithm achieves an approximation ratio of $\rho (n)$, we call it a $\rho (n)$-approximation algorithm.

An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value $\varepsilon > 0$ such that for any fixed $\varepsilon $, the scheme is a $(1+ \varepsilon )$-approximation algorithm.

We say that an approximation scheme is a polynomial-time approximation scheme (PTAS) if for any fixed $\varepsilon > 0$, the scheme runs in time polynomial in the size $n$ of its input instance($T(n,\frac{1}{\varepsilon})=O(n^{\frac{1}{\varepsilon}})$).
efficient polynomial-time approximation scheme (EPTAS) if $T(n,\frac{1}{\varepsilon})=poly(n)f(\frac{1}{\varepsilon})$

fully polynomial-time approximation scheme (FPTAS) if $T(n,\frac{1}{\varepsilon})=poly(n)poly(\frac{1}{\varepsilon})$

Examples

Bin Packing Problem

Description

Given $n$ items with size $s_1,s_2,…,s_n(0\leq s_i\leq 1)$, the Bin Packing Problem asks to use fewest bins with unit capacity to pack all the items.

Next-Fit (2-approximation)

• Always select the next item.
• Select the current bin to put in.
• If the current bin is full, create a new bin and continue.

Theorem

• Let $M$ be the optimal number of bins required to pack a list $I$ of items. Then next fit never uses more than $2M – 1$ bins. There exist sequences such that next fit uses $2M – 1$ bins.
• If Next Fit generates $2M$ (or $2M+1$) bins, then the optimal solution must generate at least $M+1$ bins.

First-Fit (1.7-approximation)

• Always select the next item.
• Scan for the first bin that is large enough to fit the current item and select it.
• If no bin is large enough, create a new bin and continue.

Theorem

• Let $M$ be the optimal number of bins required to pack a list $I$ of items. Then first fit never uses more than $17M / 10$ bins. There exist sequences such that first fit uses $17(M – 1) / 10$ bins.

Best-Fit (1.7-approximation)

• Always select the next item.
• Select a bin with the smallest remaining capacity to fit the current item.
• If no bin is large enough, create a new bin and continue.

Worst-Fit (2-approximation)

• Always select the next item.
• Select a bin with the largest remaining capacity to fit the current item.
• If no bin is large enough, create a new bin and continue.

Online Algorithms

• Place an item before processing the next one, and can NOT change decision.
• All the algorithms above are online algorithms.

Theorem

• There are inputs that force any on-line bin-packing algorithm to use at least $5/3$ the optimal number of bins.

First-Fit Decreasing (1.5-approximation)

• Sort the items in decreasing order of size.
• First Fit.

Theorem

$$FFD(I)\ or\ BFD(I)\leq \frac{11}{9}OPT(I)+\frac{6}{9} $$$$ \frac{FFD(I)}{OPT(I)}\leq \frac{\lfloor\frac{11}{9}OPT(I)+\frac{6}{9}\rfloor}{OPT(I)}\leq \frac{3}{2}$$

Knapsack Problem

Description

Given a set consisting of $N$ items, where the $i$-th item has weight $w_i$ and value $v_i$, and a knapsack capacity $c$, The task is to find a subset of items with the maximum total value such that its total size does not exceed the capacity $c$.

Fractional Version

• An item can be divided into mutiple fractions.
• So we always select the one with maximum $\frac{v}{w}$ ratio.
• The last one we choose $xv_b$, in which $x$ satisfies $0\leq x=\frac{w_{remain}}{w_b}\leq 1$

Theorem

• We have$$OPT_{Frac}= v_1+v_2+\cdots + v_{b-1} +xv_b $$$$ v1+v2+\cdots + v_{b-1}=OPT_{Frac}-xv_b\geq OPT_{Frac}-v_b$$$$v_1+v_2+\cdots + v_{b-1} +v_b\geq OPT_{Frac}$$
• And we have at least one of $\sum_{i=1}{b-1}v_i$ ,and $v_b$ is greater than $OPT_{Frac}/2$.

0-1 Version

• We can only select an item or not.
  • $A_1$:Select the item with maximum value(profit).
  • $A_2$:Select the item with maximum efficiency(profit denisty).

Theorem

We define $A_0$ as the optimal one of $A_1$ and $A_2$.
We have:$$A_0\geq OPT_{Frac}/2\geq OPT_{0-1}/2$$

So it is a 2-approximation algorithm.

A Dynamic Programming Approach

• We define $W_{i,p}$ as the minimum capacity to reach a total value of $p$ within the first $i$ items.

$$W_{i,p}=\begin{cases}\infty \quad i\ =\ 0 \\ W_{i-1,p}\quad v_i>p \\ max\lbraceW_{i-1,p},W_{i-1,p-v_i}+w_i}\quad otherwise\end{cases}$$

Theorem

• The time complexity of this algorithm is $O(N\sum v)\leq O(n^2v_{max})$

K-Center Problem

Description

Given $n$ sites $s_1,s_2,…,s_n$,a constant $k$ and a distance function $d(s_i,s_j)$, the problem asks to find $k$ sites in the plane so as to minimize the maximum distance from a site to its nearest site.

• What is distance?
  • $dist(x,x)=0$
  • $dist(x,y)=dist(y,x)$
  • $dist(x,y)\leq dist(x,z)+dist(z,y)$

Solutions

• Base case:

  • If $k=1$, select any site $s$ , $max(dist(s,s_i))=r\leq 2r_{opt}$.

• Assume we have the $r_{opt}$:

  • while there exists some uncovered sites:
    • 1.pick an abitrary uncovered site $a$ as a center.
    • 2.mark all the sites $s$ that $dist(s,a)\leq r_{opt} as covered$
  • $c$ = set of center
  • if $|c|\leq k$, done.
  • else : there exist $\leq k+1$ sites $s_1,s_2$ such that $dist(s_1,s_2)\geq 2r_{opt}$.
    How can we get $r_{opt}$?

r_max=max of dist(s_i,s_j)
binary search the r in [0,r_max]
if k centers found with 2r: go down
if k centers not found with 2r: go up

The returned $r$ is 2-approximation.
A smarter solution

Greedy():
c={s_i}
for i = 2 to k:
    select the site with maximum dist(s_j,c_i-1)
    c.append(s_j)
return c_k

We have:

• $dist(s,c)=min_{for \ c \isin C}\lbracedist(s,c)\rbrace$
• $r(c_1)\geq r(c_2)\geq \cdots \geq r(c_k)$
• The algorithm returns a set $C$ of $K$ centers such that $r© \leq 2r(C_{opt})$ where $C_{opt}$ is an optimal set of $K$ centers.
• Unless $P = NP$, there is no $\rho$ -approximation for center-selection problem for any $\rho < 2$.

Theorem

Unless $P = NP$, there is no $\rho$ -approximation for center-selection problem for any $\rho < 2$.