An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.
ASJC Scopus subject areas
- Computational Theory and Mathematics
- Algebra and Number Theory
- Theoretical Computer Science
- Information Systems