Approximation Algorithms for Decision Trees - Saettler, Aline; Laber, Eduardo S. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2018: Anais do XXXI Concurso de Teses e Dissertações, 2018)
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.