Paper Info
Title
Deterministic versus randomized adaptive test cover.
Abstract
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.
Year
DOI
Venue
2016
10.1016/j.tcs.2016.09.019
Theor. Comput. Sci.
Keywords
Field
DocType
Combinatorial search,Randomization,Game theory,LP duality,Set cover,Fractional graph theory
Set cover problem,Discrete mathematics,Combinatorics,Vertex (geometry),Hypergraph,Computerized adaptive testing,Logarithm,Time complexity,Combinatorial search,Mathematics,Binary number
Journal
Volume
Issue
ISSN
653
C
0304-3975
Citations 
PageRank 
References 
0
0.34
11
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99