Article ID: | iaor20174404 |
Volume: | 79 |
Issue: | 3 |
Start Page Number: | 886 |
End Page Number: | 908 |
Publication Date: | Nov 2017 |
Journal: | Algorithmica |
Authors: | Laber Eduardo, Cicalese Ferdinando, Saettler Aline |
Keywords: | optimization, economics, heuristics |
We characterize the best possible trade‐off achievable when optimizing the construction of a decision tree with respect to both the worst and the expected cost. It is known that a decision tree achieving the minimum possible worst case cost can behave very poorly in expectation (even exponentially worse than the optimal), and the vice versa is also true. Led by applications where deciding which optimization criterion might not be easy, several authors recently have focussed on the bicriteria optimization of decision trees. Here we sharply define the limits of the best possible trade‐offs between expected and worst case cost. More precisely, we show that for every