کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952449 | 1442032 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Deterministic versus randomized adaptive test cover
ترجمه فارسی عنوان
جلد آزمون تطبیقی تصادفی در مقابل تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In a combinatorial search problem with binary tests, we are given a set of elements (vertices) and a hypergraph of possible tests (hyperedges), and the goal is to find an unknown target element using a minimum number of tests. We explore the expected test number of randomized strategies. Our main results are that the ratio of the randomized and deterministic test numbers can be logarithmic in the number of elements, that the optimal deterministic test number can be approximated (in polynomial time) only within a logarithmic factor, whereas an approximation ratio 2 can be achieved in the randomized case, and that optimal randomized strategies can be efficiently constructed at least for special classes of graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 653, 15 November 2016, Pages 42-52
Journal: Theoretical Computer Science - Volume 653, 15 November 2016, Pages 42-52
نویسندگان
Peter Damaschke,