Correction to: Trading Off Worst and Expected Cost in Decision Tree Problems

This erratum fixes a technical problem in the paper published in Algorithmica, Volume 79, Number 3, November 2017, pp. 886-908. Theorem 1 of this paper gives upper bounds on both worst testing cost and expected testing cost of the decision tree built by Algorithm 1. Although the statement is correct, the proof presented in the paper has a problem. The proof relies on the analysis of a nonlinear program (NLP) given by Eqs. (5)-(9), which is not convex as mistakenly proved in Appendix A. 2. In this erratum we present a correct proof of Theorem 1. Instead of analyzing the NLP we analyze a related linear program.