0
$\begingroup$

Sorry if my question is banal. Consider an approximation scheme such as FPTAS that guarantees to find a soln>(1-eps)OPT for maximization. Now consider if OPT=exp(|input|) so It easily can be seen that soln is exp(|input|) So its run-time will be exponential too(just a print of result is exponential). So can we say the condition OPT<P(|input|) is a necessary condition for any problem that we want to find an approximation scheme algorithm for that?

$\endgroup$
1
$\begingroup$

FPTAS is commonly used for optimization problems whose associated decision problem is in NP. For those problems, it is guaranteed that the optimal solution has polynomial size (that's part of the definition of NP), so this issue does not arise.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.