Next: NEAREST CODEWORD
Up: Miscellaneous
Previous: MAXIMUM BETWEENNESS
  Index
- INSTANCE:
Finite set X of objects, collection
of binary tests
.
- SOLUTION:
A decision tree t for X using the tests in T, where a decision
tree is a binary tree in which each non-leaf vertex is labelled by a
test from T, each leaf is labelled by an object from X, the edge
from a non-leaf vertex to its left son is labelled 0 and the one to
its right son is labelled 1, and, if
is the sequence of vertex and edge labels on the path from the root to
a leaf labelled by ,
then x is the unique object for which
for all j, .
- MEASURE:
Number of leaves of t.
- Bad News:
APX-hard [233].
- Comment:
Not approximable within
unless
[233].
- Garey and Johnson: MS15
Viggo Kann
2000-03-20