MAXIMUM HYPERPLANE CONSISTENCY

• 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 $w\in Q^n$ and a bias $w_0$.

• MEASURE: The number of examples that are consistent with respect to the hyperplane, i.e., $\vert\{x\in P: wx>w_0\}\vert+\vert\{x\in N: wx<w_0\}\vert$.

  
  

• 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 $n^\varepsilon$ for some $\varepsilon >0$ [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 $2^{\log^{1-\varepsilon } n}$ for any $\varepsilon >0$ unless NP$\subset$QP [35] and [17].

• Garey and Johnson: Similar to MP6