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.


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.