Precedence-Constrained Decision Trees and CoveringsResearch Paper
In the Optimal Decision Tree problem an unknown target hypothesis from a finite set of hypotheses must be identified by adaptively performing tests from a family of tests; each test partitions and its reply reveals the block that contains . The problem goes back to Garey and Graham (1974) and appears in medical diagnosis, troubleshooting…