【ADS】Approximation

发表于 | 分类于 ， | | 阅读次数:

Approximation ratio

【Definition】 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( \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.

【Definition】 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 $\epsilon​$ > 0 such that for any fixed $\epsilon​$, the scheme is a (1+ $\epsilon​$)-approximation algorithm.
We say that an approximation scheme is a polynomial-time approximation scheme (PTAS) if for any fixed $\epsilon​$ > 0, the scheme runs in time polynomial in the size n of its input instance.
eg. $O((1/ \epsilon)^2 n^3)​$ –> FPTAS (fully …) , $O(n^{\epsilon/2})​$, …

Approximate Bin Packing

Online Algorithms

next fit

1
2
3
4
5
6
7
8
9
10
void NextFit ( )
{   read item1;
    while ( read item2 ) {
        if ( item2 can be packed in the same bin as item1 )
	place item2 in the bin;
        else
	create a new bin for item2;
        item1 = item2;
    } /* end-while */
}

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.

first fit

1
2
3
4
5
6
7
8
9
void FirstFit ( )
{   while ( read item ) {
        scan for the first bin that is large enough for item;
        if ( found )
	place item in that bin;
        else
	create a new bin for item;
    } /* end-while */
}

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


Off-line Algorithm

first fit decreasing

Let M be the optimal number of bins required to pack a list I of items. Then first fit decreasing never uses more than 11M / 9 + 6/9 bins. There exist sequences such that first fit decreasing uses 11M / 9 + 6/9 bins.

best fit decreasing


Exercises

ex1