1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you give an example? Problems in NP (i.e. whose decision problems are in NP) can always be solved exactly in exponential time (i.e. $2^{n^{O(1)}}$). $\endgroup$ – Yuval Filmus Oct 18 '16 at 20:53
  • $\begingroup$ Relaxed in which way? $\endgroup$ – Raphael Oct 18 '16 at 22:27
  • $\begingroup$ So.... should we close or delete this question? Can you edit it into what you actually want to know? $\endgroup$ – Raphael Oct 18 '16 at 22:27
  • $\begingroup$ Raphael, by "relaxed" I meant removed. I don't care about the scaling of time with problem size. Only about the scaling with the relative error. Does it make sense? $\endgroup$ – P. Trinli Oct 19 '16 at 17:34
  • $\begingroup$ Yuval, I can't give an example - I am looking for one. Basically, I want to find problems admitting the same scaling in relative error as FPTAS, but that are not in FPTAS (more precisely, do not admit FPTAS...). $\endgroup$ – P. Trinli Oct 19 '16 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.