1
$\begingroup$

I don't understand the exact relation between between FPT and FPTAS. Specifically, given an optimization problem P with fptas A does that imply that for any parameter (a computable map from the input to the integers) there is an FPT algorithm? It's standard that given an FPTAS, there is an FPT algorithm parameterized by the solution cost. (see: Why are all problems in FPTAS also in FPT?).

Does the existence of an FPTAS have any bearing on the FPT status of a problem with given (i.e. not necessarily solution cost) parameter k? Thanks.

$\endgroup$
  • $\begingroup$ Why do you expect there to be such a connection? The acronyms might look similar but they stand for two very different concepts. $\endgroup$ – Yuval Filmus Sep 3 '17 at 10:56
  • $\begingroup$ I don't in general. I'm trying to show the hardness of a problem in XP for which an FPTAS is known and I'm worried I'm on a fool's errand. Namely I couldn't find (for example) a problem in scheduling on m machines with a fptas for constant m, but also W hard in the number of machines. $\endgroup$ – user46745 Sep 3 '17 at 16:17

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.