The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP0. (Note: 'L' stands for linear -- this is not the same as an L reduction! For more details see [PY88].)
Defined in [PY88], where the following was also shown:
The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].
The subclass of NPO problems that admit constant-factor approximation algorithms. (I.e., there is a polynomial-time algorithm that is guaranteed to find a solution within a constant factor of the optimum cost.)
Contains PTAS.
Equals the closure of MaxSNP and of MaxNP under PTAS reduction [KMS+99], [CT94].
Defined in [ACG+99].
The class of NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.
Defined in [AP95], where it was also shown that GLO is strictly contained in APX.
[KMS+99] showed that MaxSNP is not contained in GLO.
Has the same relation to NP as MaxSNP does to SNP.
Contains MaxPB.
The closure of MaxNP under PTAS reduction is APX [KMS+99], [CT94].
[Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic.
Then SNP is the class of decision problems reducible to a graph-theoretic predicate with only universal quantifiers over vertices, no existential quantifiers. As an example, k-SAT (CNF satisfiability with at most k literals per clause, for k a constant) is in SNP. But general SAT is not in SNP, basically because we're not allowed to say, "There exists a literal in this clause that satisfies the clause."
Contains MMSNP.
See also: MaxSNP.