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. :)

Improve this question
$\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$
    – Chandra Chekuri
    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$
    – Suresh Venkat
    Apr 25, 2015 at 5:51

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
$\begingroup$

$MaxSNP=APX$. This is according to Wikipedia

Improve this answer
$\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 that you have read and understand our privacy policy and code of conduct.

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