Class Description

MaxSNP₀: Generating Class of MaxSNP

The class of function problems expressible as "find a relation such that the set of k-tuples for which a given SNP predicate holds has maximum cardinality."

For example (see [Pap94]), the Max-Cut problem can be expressed as follows:

Given a graph G, find a subset S of vertices that maximizes the number of pairs (u,v) of vertices such that u is in S, and v is not in S, and G has an edge from u to v.

Defined in [PY88].

Linked From

MaxSNP: Maximization SNP

The class of optimization problems reducible by an "L-reduction" to a problem in MaxSNP₀. (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:

• Max3SAT is MaxSNP-complete. (Max3SAT is the problem of finding an assignment that maximizes the number of satisfied clauses in a CNF formula with at most 3 literals per clause.)
• Any problem in MaxSNP can be approximated to within a fixed ratio.

The closure of MaxSNP under PTAS reduction is APX [KMS+99], [CT94].

More about...