Approximation Algorithms

Recently I started studying Approximation Algorithms in details. Though this area was touched in our UG Algo course, the browsing was really nominal. Let me introduce some basic terms in Approx Algo for future references:

Some NPC problems allow poly-time algo that achieves smaller approximation ratios by using more and more computation time. Here comes the notion of Approximation Scheme.

It provides (1+e)-Approximation Algo for each e>0.

PTAS(Polynomial Time Approximation Scheme): For any fixed e, the scheme runs in polynomial in the size of the input instance, not in p(1/e).

FPTAS(Fully PTAS): For any fixed e, the scheme runs in polynomial in the size of the input instance as well as 1/e.

APTAS(Asymptotic PTAS):

p.OPT(I)+d -> 1 as OPT(I)-> infinity, Asymptotic Guarantee

if d=0, it is PTAS.


APTAS can run in linear in n, but exponentially on e. Its output never exceeds (1+e)OPT(I)+f(e).