کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949609 1440197 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal ordering of statistically dependent tests
ترجمه فارسی عنوان
ترتیب بهینه از آزمون های آماری وابسته
کلمات کلیدی
مشکل ترتیب تست، تشخیص شی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 17-31
نویسندگان
, , , , ,