Next: MAXIMUM KNAPSACK
Up: Mathematical Programming
Previous: MINIMUM UNSATISFYING LINEAR SUBSYSTEM
  Index
- 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 NP
QP [35] and
[17].
- Garey and Johnson: Similar to MP6
Viggo Kann
2000-03-20