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.
Titolo: | Correction to: Trading Off Worst and Expected Cost in Decision Tree Problems |
Autori: | |
Data di pubblicazione: | 2018 |
Rivista: | |
Handle: | http://hdl.handle.net/11562/1023489 |
Appare nelle tipologie: | 01.01 Articolo in Rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Cicalese2018_Article_CorrectionToTradingOffWorstAnd.pdf | Versione dell'editore | Accesso ristretto | Utenti riconosciuti Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.