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$
3
  • 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$ Jan 23, 2015 at 14:21
  • $\begingroup$ Thanks a lot for your reply. I really appreciate your effort. $\endgroup$
    – user1105
    Feb 3, 2015 at 14:58
  • $\begingroup$ @ChandraChekuri comment -> answer ? $\endgroup$ Apr 25, 2015 at 5:51

2 Answers 2

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.

$\endgroup$
0
$\begingroup$

$MaxSNP=APX$. This is according to Wikipedia

$\endgroup$
1
  • 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, 2015 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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