MP12 M AXIMUM H YPERPLANE C ONSISTENCY

     
• I NSTANCE : Finite sets P and N of integer n -vectors. P consists of positive examples and N of negative examples.
• S OLUTION : A hyperplane specified by a normal vector and a bias .
• M EASURE : The number of examples that are consistent with respect to the hyperplane, i.e., .

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