Class Description

EPTAS: Efficient Polynomial-Time Approximation Scheme

The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.

Contains FPTAS and is contained in PTAS.

Defined in [CT97], where the following was also shown:

• If FPT = XP_uniform then EPTAS = PTAS.
• If EPTAS = PTAS then FPT = W[P].
• If FPT is strictly contained in W[1], then there is a natural problem that is in PTAS but not in EPTAS. (See [CT97] for the statement of the problem, since it's not that natural.)

Linked From

FPT: Fixed-Parameter Tractable

The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.

The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].

To separate FPT and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)n^O(1), where f is a computable function and n is the size of the formula.

Contained in FPT_nu, W[1], and FPR.

Contains FPTAS [CC97], as well as FPT_su.

Contains EPTAS unless FPT = W[1] [Baz95].

More about...