Problems in FPTAS require time which is (at most) polynomial in problem size. Suppose this last requirement is relaxed. What is the corresponding approximability class and where can one read about it? To be more specific, I am interested in learning about problems that can be approximated in time that scales polynomially with (inverse) relative error regardless of how it scales with problem size.
Second attempt. Consider an instance of some optimization problem having size N. From now on, N is fixed. Consider an algorithm A that produces a solution with a relative error of epsilon after time T(epsilon). I am interested in scaling of T in 1/epsilon. In particular, I wonder if there is a (known? named?) class of problems that admit algorithms with T(epsilon) bounded by a polynomial in 1/epsilon (for each N). Clearly, near epsilon=0 power-law scaling of T(1/epsilon) breaks down as T reaches a finite limit for small epsilon (as was rightfully pointed out below by Yuval). Likewise, for very large epsilon T is not defined (no approximation is worse than the worst one). My question is if T can remain a power-law in 1/epsilon for “most of” epsilon’s range. I guess any instance in FPTAS provides an example. Are there instances not in FPTAS?