Trading Off Worst and Expected Cost in Decision Tree Problems

Trading Off Worst and Expected Cost in Decision Tree Problems

0.00 Avg rating0 Votes
Article ID: iaor20174404
Volume: 79
Issue: 3
Start Page Number: 886
End Page Number: 908
Publication Date: Nov 2017
Journal: Algorithmica
Authors: , ,
Keywords: optimization, economics, heuristics
Abstract:

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 ρ > 0 equ1 there is a decision tree D with worst testing cost at most ( 1 + ρ ) OPT W equ2 and expected testing cost at most 1 1 e ρ OPT E , equ3 where OPT W equ4 and OPT E equ5 denote the minimum worst testing cost and the minimum expected testing cost of a decision tree for the given instance. We also show that this is the best possible trade‐off in the sense that there are infinitely many instances for which we cannot obtain a decision tree with both worst testing cost smaller than ( 1 + ρ ) OPT W equ6 and expected testing cost smaller than 1 1 e ρ OPT E equ7 .

Reviews

Required fields are marked *. Your email address will not be published.