3
$\begingroup$

My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, is $\mathsf{MaxSNP} = \mathsf{APX}$ or $\mathsf{MaxSNP} \subset\mathsf{APX}$?

Thanks a lot in advance. :)

$\endgroup$
  • 5
    $\begingroup$ See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507 $\endgroup$ – Chandra Chekuri Jan 23 '15 at 14:21
  • $\begingroup$ Thanks a lot for your reply. I really appreciate your effort. $\endgroup$ – user1105 Feb 3 '15 at 14:58
  • $\begingroup$ @ChandraChekuri comment -> answer ? $\endgroup$ – Suresh Venkat Apr 25 '15 at 5:51
2
$\begingroup$

See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507

Made comment into answer as per Suresh's request.

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

$MaxSNP=APX$. This is according to Wikipedia

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ That is interesting. In the Wikipedia article about $MaxSNP$ it says: "The closure of MaxSNP under PTAS reductions is APX." $\endgroup$ – R B Jan 24 '15 at 13:04

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.