Next: MAXIMUM KNAPSACK Up: Mathematical Programming Previous: MINIMUM UNSATISFYING LINEAR SUBSYSTEM Index

### 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 and a bias w0.

- MEASURE: The number of examples that are consistent with respect to the hyperplane, i.e., .

- Good News: Approximable within 2 [15].

- Bad News: APX-complete [15].

- Comment: Variation in which only one type of misclassification, either positive or negative, is allowed is not approximable within for some [15]. 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 [33] and [16].

- Garey and Johnson: Similar to MP6