期刊
DISCRETE APPLIED MATHEMATICS
卷 226, 期 -, 页码 17-31出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2017.04.009
关键词
Test ordering problem; Object detection
资金
- ISF [933/13]
- IMG4 consortium, under a MAGNET of the Israeli Ministry of Trade and Industry
- Milken Families Foundation Chair in Mathematics
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据