Next: MAXIMUM KNAPSACK
Up: Mathematical Programming
Previous: MINIMUM UNSATISFYING LINEAR SUBSYSTEM
Finite sets P and N of integer n-vectors. P consists of positive
examples and N of negative examples.
A hyperplane specified by a normal vector
and a bias .
The number of examples that are consistent with respect to the hyperplane,
- Good News:
Approximable within 2 .
- Bad News:
Variation in which only one type of misclassification, either positive
or negative, is allowed is not approximable within
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
unless NPQP  and
- Garey and Johnson: Similar to MP6