Greedy Algorithm with Weights for Decision Tree Construction

Issue title: Hardest Boolean Functions and O.B. Lupanov

Article type: Research Article

Authors: Moshkov, Mikhail Ju.

Affiliations: Division of Mathematical and Computer Sciences and Engineering, King Abdullah University of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia. mikhail.moshkov@kaust.edu.sa

Note: [] Address for correspondence: Division of Mathematical and Computer Sciences and Engineering, King Abdullah University of Science and Technology, P.O. Box 55455, Jeddah 21534, Saudi Arabia

Abstract: 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.

Keywords: Decision table, decision tree, weight, greedy algorithm

DOI: 10.3233/FI-2010-350

Journal: Fundamenta Informaticae, vol. 104, no. 3, pp. 285-292, 2010