Journal
DISCRETE APPLIED MATHEMATICS
Volume 226, Issue -, Pages 17-31Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2017.04.009
Keywords
Test ordering problem; Object detection
Categories
Funding
- ISF [933/13]
- IMG4 consortium, under a MAGNET of the Israeli Ministry of Trade and Industry
- Milken Families Foundation Chair in Mathematics
Ask authors/readers for more resources
We consider scenarios where a sequence of tests is to be applied to an object, such that one outcome of a test may be a decision to terminate the sequence (e.g. deciding that the object is faulty) without running additional tests. One seeks an ordering of the tests that is minimal in expected resource consumption. 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 show that with dependencies the optimization problem is NP-hard in the general case, and provide low-order polynomial time algorithms for special cases with non-trivial dependency structures. (C) 2017 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available