Optimal Ordering of Tests with Extreme Dependencies

Optimization of testing strategies has numerous facets. Here we examine the case where tests are one-sided perfect - thus an optimal strategy consists of a sequence of tests, and the remaining problem is to find an optimal (w.r.t. time, or any other resource) ordering of a given set of tests. In prior work, we examined conditions under which statistically independent test sequences can be optimized under precedence constraints. This paper examines conditions under which one can efficiently find an optimal ordering of tests with statistical dependencies. We provide low-order polynomial time algorithms for special cases with non-trivial dependency structures.