General techniques for developing Epsilon-approximation schemes

An approximation algorithm for solving an extremum problem is called an Epsilon-approximation algorithm if it delivers a solution with relative error Epsilon. A family of Epsilon-approximation algorithms determined for any positive Epsilon is called an Epsilon-approximation scheme.

Main ideas, general techniques and their modifications for developing fast Epsilon-approximation schemes will be described.

B.Hammer