3
$\begingroup$

All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ hardness results also give an explicit constant in their hardness proofs, or only $\mathsf{APX}-\mathsf{Hard}$ proofs do that? Are there any exceptions? Please support your answers with some examples from literature.

Thanks you.

$\endgroup$

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.