Approximation Algorithms for Decision Trees

• Aline Saettler
• Eduardo S. Laber

DOI: https://doi.org/10.5753/ctd.2018.3649

Resumo

Decision trees are a central structure in computer science, having applications in many areas. This thesis contributes to the understanding of this important structure by proving by proving theoretical bounds on its behavior and also providing algorithms to construct decision trees with much stronger guarantee and that can cope with more general situations than the solutions available in the literature.