- INSTANCE:
Finite sets
*P*and*N*of integer*n*-vectors.*P*consists of positive examples and*N*of negative examples. - SOLUTION:
A hyperplane specified by a normal vector
and a bias .
- MEASURE:
The number of examples that are consistent with respect to the hyperplane,
i.e.,
.

*Good News:*Approximable within 2 [16].*Bad News:*APX-complete [16].*Comment:*Variation in which only one type of misclassification, either positive or negative, is allowed is not approximable within for some [16]. The complementary minimization problem, where the number of misclassifications is to be minimized, is not in APX unless P=NP, and is not approximable within for any unless NPQP [35] and [17].*Garey and Johnson:*Similar to MP6